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 la lettura »
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. … Continua la lettura »
set
24
Ricavare il numero di una permutazione (ranking)
questo articolo è la continuazione del articolo sulla determinazione di una specifica permutazione e affronta il problema inverso: determinare la posizione di una specifica permutazione nell’insieme delle permutazioni ordinate lessicograficamente. Ancora qualcosa sull’interpretazione dei codici di Lehmer I singoli termini del codice di Lehmer si possono anche interpretare come il numero di elementi che si … Continua la lettura »
set
19
Determinare una specifica permutazione dall'insieme delle permutazioni
questo articolo è la continuazione del articolo precedente sulle permutazioni. Potrebbe essere necessario determinare una singola permutazione dall’insieme delle permutazioni ordinate e inutile determinarle tutte. Questo problema è più complicato del caso precedente e prima di continuare vorrei rendere noto che l’articolo non è frutto delle mie conoscenze universitarie o di conoscenze direttamente connesse che … Continua la lettura »
giu
30
Un semplice algoritmo iterativo per listare le permutazioni di un insieme di elementi
Spesso quando si lavora su algoritmi che hanno come dati di ingresso una lista di elementi si ha la necessità di testarne il comportamento su tutte le permutazioni possibili dell’insieme di ingresso. L’algoritmo seguente è probabilmente il più semplice algoritmo iterativo per listare le permutazioni di un insieme di elementi, l’algoritmo analizza semplicemente la permutazione … Continua la lettura »
