Archivio Tag: Johnson-Trotter

feb 20

Algoritmi sulle permutazioni, articolo in PDF

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 …

Continua a leggere »

Share Button

feb 18

Algoritmo degli scambi semplici (Plain changes – Johnson-Trotter)

Esecuzione dell'algoritmo degli scambi semplici su un insieme di 4 elementi

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. …

Continua a leggere »

Share Button