Ho tratto un articolo dai vari post sugli algoritmi per la generazione di permutazioni.
Gli argomenti trattati sono:
1 Algoritmo iterativo per generare permutazioni in ordine lessicografico
2 Algoritmo ricorsivo per generare permutazioni
3 Algoritmo degli scambi semplici (Plain changes – Johnson-Trotter)
4 Determinare una specifica permutazione dall’insieme delle permutazioni
4.1 I Factoradic
4.2 Interpretazione dei codici di Lehmer
4.2.1 Algoritmi per la generazione di un Factoradic
4.3 Generazione di permutazioni casuali con i factoradic
5 Ricavare il numero di una permutazione (ranking)
6 Generare permutazioni casuali (algoritmo di Fisher-Yates o Knuth shuffle)
6.1 Problemi di bias
Il testo è rilasciato sotto licenza Creative Commons
1 ping
Algoritmi sulle permutazioni, articolo in PDF « The Darshan’s Weblog
23 giugno 2010 a 19:31 (UTC 2) Link a questo commento
[...] Algoritmi sulle permutazioni, articolo in PDF Il nuovo blog contiene una versione più aggiornata di questo articolo [...]