Ho una lista di lettere, questa è solo una lista di esempi:
['a','b','c','d','e']
Come faccio a calcolare ogni combinazione della lista? Le lettere non possono essere ripetute, per esempio.
a,b,c,d,e
a,c,b,d,e
a,c,d,b,e
a,c,d,e,b
a,e,d,c,b
...
Ho una lista di lettere, questa è solo una lista di esempi:
['a','b','c','d','e']
Come faccio a calcolare ogni combinazione della lista? Le lettere non possono essere ripetute, per esempio.
a,b,c,d,e
a,c,b,d,e
a,c,d,b,e
a,c,d,e,b
a,e,d,c,b
...
La semplice risposta per Python è la libreria itertools . È tutto, hai finito.
In Ruby fa parte della classe Array.
$ irb
>> a = [1, 2, 3]
=> [1, 2, 3]
>> a.permutation.to_a
=> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Tuttavia, questa è una risposta molto noiosa e non aiuta nessuno che (nonostante il tag e io puntiamo anche ad altre lingue) sta cercando di scoprire come creare ogni permutazione di un set.
L'approccio di base a questo ti itera su ogni elemento nel set e genera le permutazioni di tutto il resto del set.
L'approccio semplice a questo è un modello di backtracking . Il metodo do() fa ciò che si vuole fare, stamparlo o calcolarlo ulteriormente.
exchange (x, y) {
return y, x;
}
generate (n) {
int c;
if(n = 1) do();
for (c = 1; c < n; c++)
{ exchange(c,n); generate(n-1); exchange(c,n); }
}
Questo algoritmo fa 2n! di scambi.
Il metodo di heap è un semplice approccio ricorsivo. Considera quanto segue
-*-*-*-*-*- | | | | | -*-|-*-|-*- | | ---*---*--- a b c a b c b a a c c b c c b b a a
Inizia con abc, quindi scambia 1 e 2, quindi 1, 3, quindi 1, 2, quindi 1, 3, quindi 1, 2. Se hai 4 elementi, dopo che questa sequenza di pattern è completata scambia 1, 4 - quindi un'altra sequenza e 2, 4 e un'altra sequenza e 3, 4.
Se era 5, allora ripetevi la sequenza di 4, e poi fai 1, 5, poi 2, 5, poi 3, 5. Dovresti ottenere l'idea.
Scrivere questo in modo ricorsivo è piuttosto semplice.
generate(n) {
int c;
if (n == 1) { do(); return; }
for (c = 1; c <= n; c++) {
generate(n-1);
exchange(n % 2 ? 1 : c, n)
}
}
Se vuoi davvero saperne di più, The Art of Computer Programming Il volume 4, Algoritmi combinatori , sezione 7.2.1.2 è intitolato "Generazione di tutti Permutazioni "che vanno profondamente in matematica.
Leggi altre domande sui tag python combinatorics