Algoritmo per il calcolo diretto di permutazioni

Tweet

Le permutazioni, come le combinazioni, di cui ci occuperemo in un prossimo topic, sono concetti matematici particolarmente importanti in quanto alla base di numerosi algoritmi utilizzati nei software più disparati.
Per tale motivo, è molto utile disporre di un buon algoritmo per la generazione di questi oggetti matematici.
In particolare, di seguito, sarà descritto un algoritmo per calcolare in modo diretto una specifica permutazione a partire dalla sua posizione nella lista delle permutazioni con ordine lessicografico (o ordine da dizionario).
Ora, in generale, le permutazioni, come le combinazioni, sono oggetti matematici i cui elementi possono appartenere agli insiemi più disparati. Noi, nel seguito, senza perdere di generalità, ci riferiremo a permutazioni i cui elementi sono numeri interi che vanno da 0 alla lunghezza della permutazione.
In tal modo, quindi, dire che l'elenco delle permutazioni è ordinato lessicograficamente equivale a dire che le permutazioni, interpretando ciascuna di essa nella sua interezza come un unico numero intero, sono elencate in ordine crescente.
Per descrivere l'algoritmo in oggetto, ci riferiremo, per comodità, ad un caso specifico; fermo restando la sua validità nel caso generale.
Il caso specifico a cui ci riferiremo è quello relativo a n=4; per cui, per tale caso, numerandole progressivamente a partire da zero, le permutazioni sono 24 e sono le seguenti:

 0: [0, 1, 2, 3]
 1: [0, 1, 3, 2]
 2: [0, 2, 1, 3]
 3: [0, 2, 3, 1]
 4: [0, 3, 1, 2]
 5: [0, 3, 2, 1]
 6: [1, 0, 2, 3]
 7: [1, 0, 3, 2]
 8: [1, 2, 0, 3]
 9: [1, 2, 3, 0]
10: [1, 3, 0, 2]
11: [1, 3, 2, 0]
12: [2, 0, 1, 3]
13: [2, 0, 3, 1]
14: [2, 1, 0, 3]
15: [2, 1, 3, 0]
16: [2, 3, 0, 1]
17: [2, 3, 1, 0]
18: [3, 0, 1, 2]
19: [3, 0, 2, 1]
20: [3, 1, 0, 2]
21: [3, 1, 2, 0]
22: [3, 2, 0, 1]
23: [3, 2, 1, 0]

Un ruolo cruciale nel nostro algoritmo è svolto dal factoradic (detto anche sistema di numero fattoriale o base fattoriale). Il factoradic è una rappresentazione alternativa di un numero intero.
Vediamo di cosa si tratta. Allo scopo, per il nostro caso n=4, è facile mostrare che il numero 11 può essere rappresentato nel seguente modo:

11 = (1 * 3!) + (2 * 2!) + (1 * 1!) + (0 * 0!) = (1 * 6) + (2 * 2) + (1 * 1) + (0 * 1) = 6 + 4 + 1 + 0 = 11

Ed il suo factoradic risulta essere: [1, 2, 1, 0].

Più in generale, fissato n, è possibile dimostrare che qualsiasi numero compreso tra 0 e (n! - 1), estremi inclusi, può essere rappresentato nella forma appena vista; ossia che $\forall$ index=$0, \cdots, (n! - 1), \exists c_0, c_1, \cdots, c_{n-1}$ interi compresi tra 0 e n-1, tali che: index = $(c_0 * (n-1)!) + (c_1 * (n-2)!) + \cdots + ((c_{n-1}) * 0!)$ e [$c_0, c_1, \cdots, c_{n-1}$] è il factoradic di index con il fissato n.

Per il calcolo del factoradic di index può essere utilizzato il seguente snippet:

for (int i=1; i<=n; ++i) {
     factoradic[n-i] = index % i;
     index /= i;
}

Tornando all'esempio precedente, la lista dei facoradic risulta essere la seguente:

 0: [0, 0, 0, 0]
 1: [0, 0, 1, 0]
 2: [0, 1, 0, 0]
 3: [0, 1, 1, 0]
 4: [0, 2, 0, 0]
 5: [0, 2, 1, 0]
 6: [1, 0, 0, 0]
 7: [1, 0, 1, 0]
 8: [1, 1, 0, 0]
 9: [1, 1, 1, 0]
10: [1, 2, 0, 0]
11: [1, 2, 1, 0]
12: [2, 0, 0, 0]
13: [2, 0, 1, 0]
14: [2, 1, 0, 0]
15: [2, 1, 1, 0]
16: [2, 2, 0, 0]
17: [2, 2, 1, 0]
18: [3, 0, 0, 0]
19: [3, 0, 1, 0]
20: [3, 1, 0, 0]
21: [3, 1, 1, 0]
22: [3, 2, 0, 0]
23: [3, 2, 1, 0]

Una volta calcolato il factoradic è possibile calcolare la corrispondente permutazione.
Per illustrare come calcolare la permutazione partendo dal factoradic appena calcolato, continuiamo ad utilizzare l'esempio che stavamo considerando precedentemente con n=4, index=11 e factoradic=[1, 2, 1, 0].

       index   factoradic     permutation
        11 -> [1, 2, 1, 0] -> [1, 3, 2, 0]

factoradic:      1                        2            1        0
                       |                      |            |        |
                 [0, 1, 2, 3] -> [0, 2, 3] -> [0, 2] -> [0]
                       |                      |            |        |
permutation:    1                      3            2        0

Lo snippet relativo al calcolo della permutazione a partire dal factoradic, in pseudo-codice, è il seguente:

for (int i=0; i<n; i++)
      temp[i] = i;

for (int i=0; i<n; i++) {
      permutation[i] = temp[factoradic[i]];
      remove(temp[factoradic[i]]); // rimuove l'elemento da temp diminuendo anche la dimensione di tale array
}

In tal modo l'obbiettivo è raggiunto: partendo dall'indice e calcolando il factoradic è stato possibile risalire alla permutazione associata.
Inoltre, l'algoritmo illustrato è anche invertibile; ossia, partendo da una determinata permutazione è possibile calcolare il relativo factoradic e da questi risalire all'indice della permutazione. Vediamo come.
Innanzitutto, vediamo come è possibile calcolare il factoradic partendo da una specifica permutazione.
Allo scopo, consideriamo ancora la permutazione: [1, 3, 2, 0].
Consideriamo il primo elemento e contiamo il numero di elementi che lo seguono che sono più piccoli di esso (scrivendo tale numero sotto l'elemento considerato:

[1]   [3, 2, 0]
[1]

Ora, ripetiamo questo processo sui restanti elementi [3, 2, 0]:

[1, 3]   [2, 0]
[1, 2]

Ripetiamo ancora sui restanti:

[1, 3, 2]   [0]
[1, 2, 1]

E sull'ultimo:

[1, 3, 2, 0]
[1, 2, 1, 0]

In tal modo otteniamo il factoradic che volevamo calcolare.
A questo punto è immediato risalire all'indice della permutazione in quanto, proprio per come è stato definito il factoradic, risulta che esso è uguale a:

(1 * 3!) + (2 * 2!) + (1 * 1!) + (0 * 0!) = 6 + 4 + 1 + 0 = 11

In questo modo abbiamo visto anche il funzionamento inverso.
Altro notevole pregio di tale algoritmo è che con esso è immediato realizzare un programma per il calcolo delle permutazioni che lavora in parallelo.
Per il futuro mi riservo di pubblicare sul mio sito il codice sogente di un'implementazione Java relativa a quanto esposto.

Riferimenti Web:

http://msdn.microsoft.com/en-us/magazine/cc163513.aspx

http://msdn.microsoft.com/it-it/magazine/cc163513.aspx

http://msdn.microsoft.com/en-us/library/Aa302371