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 …
Archivio Tag: Johnson-Trotter
feb 18
Algoritmo degli scambi semplici (Plain changes – Johnson-Trotter)
L’algoritmo degli scambi semplici è l’algoritmo più efficiente per generare permutazioni, le permutazioni vengono generate con un singolo scambio, quindi costituiscono un codice Gray. L’algoritmo è stato ideato nel diciassettesimo secolo in Inghilterra da parte di alcuni suonatori di campane che avevano sviluppato il buffo passatempo di suonare le campane secondo tutte le permutazioni possibili. …