Riapro una discussione che è andata cancellata insieme agli altri thread delle 24 ore precedenti la chiusura del forum.
Esistono uno o più algoritmi sufficientemente efficienti da essere in grado di elencare tutte le possibili permutazioni, disposizioni o combinazioni di n presi ad m ad m con o senza ripetizioni (dove n ed m sono numeri non troppo grandi)?
Ho scritto una funzione in Python che calcoli le disposizioni con ripetizione per n simboli dati, basata su una funzione random che viene eseguita fino al raggiungimento del totale delle disposizioni n^m. L'esecuzione è molto veloce, ma l'algoritmo non mi sembra dei migliori.
codice:
n=("a","b","c")
m=4
d=[]

from math import pow
t=pow(len(n),m)

from random import randint
while len(d)<t:
	e=""
	for i in range(m):
		e+=str(randint(0,len(n)-1))
	for i in range(len(n)):
		e=e.replace(str(i),n&#091;i])
	if not d.__contains__(e):
		d.append(e)

d.sort()
d=&#091;"%d - %s" % (d.index(e)+1,e) for e in d]
for i in d: print i
C'era stato chi mi aveva chiesto di trascriverle, quindi riporto le formule per calcolare il numero di disposizioni, permutazioni e combinazioni (per comodità evito la notazione con i coefficienti binomiali).
Per calcolare il numero di disposizioni: D=n!/(n-m)!
Permutazioni: P=n!
Combinazioni: C=n!/(m!(n-m)!)
Disposizioni con ripetizione: D'=n^m (n elevato a m)
Permutazioni con ripetizione: P'=n!/m!
Combinazioni con ripetizione: (n-1+m)!/((n-1)!m!)