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.
Come si affronta questo problema? ogni informatico sano di mente scarterebbe nel giro di un paio di secondi la possibilità di generare tutte le permutazioni fino a quella cercata (ma non preoccupatevi…se non avete scartato entro due secondi potete comunque laurearvi in molte università e dire in giro di essere degli ingegneri del software).
Dunque, riformuliamo il problema: come fare per determinare una specifica permutazione in tempo costante o quantomeno proporzionale al numero di elementi del dominio?
La soluzione risiede nell’uso dei factoradic (termine che non so proprio come tradurre in italiano)
I Factoradic
Di solito un numero viene rappresentato come un polinomio di potenze della base
inquanto le potenze dei primi n numeri costituiscono una base che permette di rappresentare univocamente un numero con un polinomio.
Anche i fattoriali dei primi n numeri costituiscono una base , quindi è possibile rappresentare univocamente un numero come polinomio dei fattoriali della base
questa rappresentazione è detta factoradic. L’univocità di questa rappresentazione è garantita dal fatto che la somma dei primi n fattoriali moltiplicati per il loro indice è sempre il fattoriale successivo meno 1.
caratteristica fondamentale dei factoradic è il costistuire un codice che permette di associare al numero n rappresentato la n-esima permutazione dell’insieme degli elementi della base, questo “codice di traduzione” viene chiamato codice di Lehmer
n | Factoradic | Permutazione |
0 | 0000 | [ 1,2,3,4 ] |
1 | 0010 | [ 1,2,4,3 ] |
2 | 0100 | [ 1,3,2,4 ] |
3 | 0110 | [ 1,3,4,2 ] |
4 | 0200 | [ 1,4,2,3 ] |
5 | 0210 | [ 1,4,3,2 ] |
6 | 1000 | [ 2,1,3,4 ] |
7 | 1010 | [ 2,1,4,3 ] |
8 | 1100 | [ 2,3,1,4 ] |
9 | 1110 | [ 2,3,4,1 ] |
10 | 1200 | [ 2,4,1,3 ] |
11 | 1210 | [ 2,4,3,1 ] |
12 | 2000 | [ 3,1,2,4 ] |
13 | 2010 | [ 3,1,4,2 ] |
14 | 2100 | [ 3,2,1,4 ] |
15 | 2110 | [ 3,2,4,1 ] |
16 | 2200 | [ 3,4,1,2 ] |
17 | 2210 | [ 3,4,2,1 ] |
18 | 3000 | [ 4,1,2,3 ] |
19 | 3010 | [ 4,1,3,2 ] |
20 | 3100 | [ 4,2,1,3 ] |
21 | 3110 | [ 4,2,3,1 ] |
22 | 3200 | [ 4,3,1,2 ] |
23 | 3210 | [ 4,3,2,1 ] |
Interpretazione dei codici di Lehmer, generazione della permutazione associata
Dal factoradic si può ottenere la permutazione invertendo i singoli elementi o i segmenti della permutazione di base [1,2,3,4] con gli elementi a destra usando l’elemento del codice di Lehmer come lunghezza del segmento da spostare.
Per esempio
- il codice 0110 indica che, partendo dalla permutazione di base, si deve invertire l’elemento 2 e poi l’elemento 3 ottenendo la permutazione [1,3,4,2]
- il codice 0200 indica di invertire l’elemento 2 e il successivo (il numero due indica questo: due elementi di uno e NON un elemento di due) ottenendo [1,4,2,3]
Algoritmo per la generazione di un Factoradic
l’algoritmo di generazione è molto semplice: le singole componenti vengono calcolate con l’operatore modulo
public static int[] factoradic(int numero, int base){ assert (base>1 && numero >= 0 ); int[] f = new int[base]; for (int j = 1; j <= base; ++j) { f[base-j] = numero % j; numero /= j; } return f; }
è lo stesso tipo di algoritmo che si usa per convertire un numero decimale in una base diversa, si va dividendo il numero per la base e i resti delle divisioni vanno a costituire il numero nella base di arrivo, solo che in questo caso la base non è costante ma decresce.
Dal Factoradic alla permutazione
il codice va inserito nella classe definita nel post precedente
public int[] permutazione(int n){ int[] lehmer=MyMath.factoradic(n, len); int a; //creo la permutazione di base for (a = 0; a < len; a++)elementi[a] = a + 1; //applico il codice for (a = 0; a < len; a++){ if(lehmer[a]==1) //caso banale, mi limito a fare uno swap swap(a, a+1); else if(lehmer[a]>1){ //caso generico, sposto un segmento int k=lehmer[a]+a; int buffer=elementi[k]; while(k>;a){ swap(k-1,k); k--; } elementi[a]=buffer; } } return elementi; }
Generazione di permutazioni casuali
Dando come input alla funzione precedente un numero casuale compreso nel numero di permutazioni si ottiene ovviamente una permutazione casuale
6 comments
1 ping
Vai al modulo dei commenti ↓
luca
24 settembre 2009 a 09:49 (UTC 2) Link a questo commento
L’articolo e` molto chiaro. Mi interesserebbe molto un articolo dello stesso autore relativo ad un algoritmo inverso: da permutazione_ennesima ricavare N o quantomeno ricavare il factoradic dalla permutazione (dal quale poi si puo ricavare N).
Grazie, Luca
thedarshan
24 settembre 2009 a 11:57 (UTC 2) Link a questo commento
anche io volevo completare l’argomento affrontando anche la funzione di ranking, ma trovare documentazione è ancora più difficile che nel caso precedente (per il quale mi sono basato su un pessimo articolo della microsoft e su wikipedia).
contavo di procurarmi il testo di Knuth sulla programmazione e partire da quello.
comunque ci sto lavorando, e l’articolo sarà sicuramente dello stesso autore, perchè sono l’unico autore del blog.
luca
24 settembre 2009 a 13:19 (UTC 2) Link a questo commento
Una indicazione di come realizzare l’algoritmo inverso si trova comunque qui:
http://en.wikipedia.org/wiki/Factoradic#Permutations
Michele
28 agosto 2019 a 18:47 (UTC 2) Link a questo commento
Non ho capito come si determina un factoradic. Nell’esempio, come si arriva a scrivere il polinomio espresso come somma di fattoriali del numero 1936.
Potete indicarmi un autore o un testo che spieghi la cosa, per favore
Vincenzo La Spesa
29 agosto 2019 a 18:59 (UTC 2) Link a questo commento
Io mi sono basato molto sul libro di Knuth, in particolare:
- Donald E. Knuth The Art of Computer Programming, Volume 2: Seminumerical
Algorithms, section 3.2.1
- Donald E. Knuth (2005), The Art of Computer Programming, Volume 4 Fascicle 2,
Generating All Tuples and Permutations ,Addison-Wesley, paragrafo 2.7.1.2, ISBN
0-201-85393-0
Ma la descrizione dei factoradic viene da un altro dal titolo “Using Permutations in .NET for Improved Systems Security” scritto da James McCaffrey, purtroppo l’articolo non è più online anche se viene citato in altri siti. Alla fine sono riuscito a pescarlo in un sito cinese, ti allego il link in pdf
http://www.thedarshan.com/home/files/41338_Using_Permutations_in_NET_for_Improved_Systems_Security.pdf
Negli ultimi 10 anni ( dio santo, questo post ha 10 anni! ) sono spuntati vari altri post sull’argomento in vari altri blog, probabilmente nessuno in italiano.
Vincenzo La Spesa
29 agosto 2019 a 20:00 (UTC 2) Link a questo commento
Quindi, veniamo all’algoritmo.
L’idea è quella di dividere il numero da convertire per la base ( che cresce di una unità ad ogni iterazione) e raccogliere i resti della divisione.
Proviamolo su 1936
1936 % 1 = 0 ( questa cifra è sempre zero)
1936 // 1 = 1936
1936 % 2 = 0
1936 // 2 = 968
968 % 3 = 2
968 // 3 = 322
322 % 4 = 2
322 // 4 = 80
80 % 5 = 0
80 // 5 = 16
16 % 6 = 4
16 // 6 = 2
2
Ricavare il numero di una permutazione (ranking) « The Darshan’s Weblog
24 settembre 2009 a 17:06 (UTC 2) Link a questo commento
[...] 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 [...]