Algoritmi per la generazione di permutazioni

Vincenzo La Spesa

20 febbraio 2010

v1.0

Indice

1 Algoritmo iterativo per generare permutazioni in ordine lessicografico 2

2 Algoritmo ricorsivo per generare permutazioni in ordine lessicografico 3

3 Algoritmo degli scambi semplici (Plain changes - Johnson-Trotter) 4

4 Determinare una specifica permutazione dall’insieme delle permutazioni 64.1 I Factoradic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.2 Interpretazione dei codici di Lehmer . . . . . . . . . . . . . . . . . . . . . 6

4.2.1 Algoritmi per la generazione di un Factoradic . . . . . . . . . . . . 84.3 Generazione di permutazioni casuali con i factoradic . . . . . . . . . . . . 9

5 Ricavare il numero di una permutazione (ranking) 9

6 Generare permutazioni casuali (algoritmo di Fisher-Yates o Knuth shuffle) 106.1 Problemi di bias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

http://thedarshan.wordpress.com/

Quest’opera e stata rilasciata sotto la licenza Creative Commons Attribuzione-Noncommerciale-Condividi allo stesso modo 2.5 Italia. Per leggere una copia della li-cenza visita il sito web http://creativecommons.org/licenses/by-nc-sa/2.5/it/ o spe-disci una lettera a Creative Commons, 171 Second Street, Suite 300, San Francisco,California, 94105, USA.

1

1 Algoritmo iterativo per generare permutazioni in ordine lessicografico

L’algoritmo seguente e probabilmente il piu semplice algoritmo iterativo per listare lepermutazioni di un insieme di elementi, analizza semplicemente la permutazione attualeper ricavarne la prossima basandosi sul fatto che le permutazioni devono seguire unordinamento lessicografico (nel caso numerico qui analizzato ogni permutazione deveessere la minima permutazione maggiore di quella corrente)

considerando la permutazione come un vettore di n elementi numerici l’algoritmodetermina la permutazione successiva nel seguente modo:

1. a partire dall’ultimo elemento scorre l’array cercando il primo elemento precedutoda un elemento minore

2. se non esiste si e giunti all’ultima permutazione possibile e l’algoritmo deve termi-nare

3. se esiste ricomincia a scorrere il vettore dalla fine cercando il primo elementomaggiore all’elemento trovato al punto1

4. si invertono gli elementi trovati al punto1 e al punto3

5. se lo scambio non e avvenuto tra elementi di livello minimo (l’ultimo e il penultimo)si ripristina l’ordinamento interno invertendo le posizioni degli elementi che sitrovano tra l’elemento trovato al punto1 e quello trovato al punto3

l’algoritmo e molto semplice e molto generico ma non e efficiente, infatti il fatto di doveranalizzare a ogni iterazione la struttura attuale del vettore ne incrementa di molto lacomplessita.

Listing 1: Algoritmo semplice

public boolean pross ima ( ) {int i = l en − 1 ;while ( i>0 && ( e lement i [ i − 1 ] >= element i [ i ] ) ) i−−;i f ( i==0)return fa l se ;int j = l en ;// ( i−1) e l ’ e lemento t r o va t o con i l c i c l o precedentewhile ( e l ement i [ j − 1 ] <= element i [ i − 1 ] ) j−−;swap( i − 1 , j − 1 ) ;i++;j = l en ;// in v e r t o g l i e l emen t i t ra i due e l emen t i s camb ia t iwhile ( i < j ) {

swap ( i − 1 , j − 1 ) ;i++;j−−;

}return true ;

}

2

1

2 Algoritmo ricorsivo per generare permutazioni in ordine lessicografico

L’uso di un algoritmo ricorsivo per la generazione di permutazioni non e particolarmen-te conveniente perche non permette di generare una permutazione per volta, e inoltrel’approccio iterativo e di perse piu veloce perche non usa memoria di stack, detto questoho deciso di includere comunque questo algoritmo come esempio “didattico”.

L’implementazione ricorsiva e una tipica applicazione dell’approccio divide et impera

Le permutazioni di un vettore di n elementi si ottengono calcolando le permutazionidel sottovettore di n-1 elementi e poi scambiando l’n-esimo elemento con ogni elemen-to del sottovettore. Il caso base e la permutazione di un vettore di due elementi che esemplicemente uno scambio

Listing 2: Algoritmo ricorsivo

static void permuta r i c o r s i vo ( int [ ] e lementi , int da , int a ){int k ;i f ( a > da ){

for ( k = a ; k >= da ; k−−){Ar r ay u t i l . swap ( elementi , k , a ) ;pe rmuta r i co r s i vo ( e lementi , da , a−1);Ar r a y u t i l . swap ( elementi , k , a ) ;

}} else{System . out . p r i n t l n ( Ar r a y u t i l . dump( e lement i ) ) ; }

}

2,1,3,4 2,1,4,3 4,1,3,2 2,4,3,11,3,2,4 1,4,2,3 1,3,4,2 4,3,2,13,1,2,4 4,1,2,3 3,1,4,2 3,4,2,13,2,1,4 4,2,1,3 3,4,1,2 3,2,4,12,3,1,4 2,4,1,3 4,3,1,2 2,3,4,1

Tabella 1: Esecuzione dell’algoritmo su un vettore di 4 elementi

1articolo originale in http://thedarshan.wordpress.com/2009/06/30/un-semplice-algoritmo-iterativo-per-listare-le-permutazioni-di-un-insieme-di-elementi/

3

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

2 L’algoritmo degli scambi semplici e stato ideato nel diciassettesimo secolo in Inghilterrada parte dei suonatori di campane che avevano sviluppato il buffo passatempo di suonarele campane secondo tutte le permutazioni possibili. 3

Le prime traccie scritte di questo algoritmo risalgono al 1653 ed e trattato in manieraestensiva nel libro Tintinnalogia del 1668 che gli dedica addirittura 60 pagine... Le primeimplementazioni informatiche documentate risalgono invece al 1962 ad opera di H. F.Trotter e al 1963 con S.M. Johnson ed e per questo che l’algoritmo e noto anche comel’algoritmo di Johnson-Trotter.

L’algoritmo opera facendo in modo che solo una coppia venga scambiata ad ognipermutazione e che la coppia sia sempre formata da elementi adiacenti.

L’idea da cui nasce l’algoritmo e che si possano generare le permutazioni di un vettoredi n elementi scegliendo dei sottovettori di n-1 elementi e facendo scorrere l’n-esimoelemento all’interno dei sottovettori.

Quando l’n-esimo ha percorso l’intero sottovettore, si calcola la prossima permuta-zione del sottovettore e si fa scorrere l’n-esimo elemento in senso contrario.

Per implementare questa procedura si usa un secondo vettore che contiene le direzionidi mobilita possibili (il vettore D) che vengono settate a 1 (mobile a destra) o a -1 (mobilea sinistra).

Un singolo elemento e mobile soltanto se nella direzione della sua mobilita (vettore D)l’elemento successivo e inferiore dell’elemento corrente (in particolare il primo elementonon e mai mobile a sinistra e l’ultimo non e mai mobile a destra).

Si usa inoltre un vettore degli scambi (vettore C) il cui n-esimo elemento rappresentail numero di elementi minori di n che stanno alla sua destra. Confrontando le variazionidel vettore C con la direzione di mobilita contenuta nel vettore D si puo ottenere loscambio da eseguire per arrivare alla permutazione successiva.

a questo punto l’algoritmo agisce in questo modo:

Finche esistono elementi mobili se ne trova il maggiore e lo si inverte con l’elemen-to successivo nella direzione di mobilita, poi si inverte la direzione di mobilita di tuttigli elementi alla sua destra

Figura 1: Esecuzione dell’algoritmo degli scambi semplici su un insieme di 4 elementi

2 Articolo originale in http://wp.me/p9RRM-6i3 altre informazioni sull’algoritmo e sulla sua origine si trovano inKnuth, Donald (2005), ”Volume 4 Fascicle 2, Generating All Tuples and Permutations”, The Art of

Computer Programming , Addison-Wesley, paragrafo 2.7.1.2, ISBN 0-201-85393-0

4

Listing 3: Implementazione del Plain Changes

/�� e l emen t i [ ]= i l v e t t o r e d e g l i e l emen t i� c [ ]= i l v e t t o r e d e g l i scambi� d []= i l v e t t o r e d e l l e d i r e z i o n i� n=dimenzione de l v e t t o r e� j=scor re i l v e t t o r e d a l l a f i n e a l l ’ i n i z i o�/

public void l i s t a l l ( ) {int n=this . l en ;do{

f l a g=true ;System . out . p r i n t l n ( Ar r a y u t i l . dump( e lement i ) ) ;j=n−1;s=0;do{

q=c [ j ]+d [ j ] ;i f ( q==1 && j==0)return ;i f (q>=0 && q!=( j +1)){

Ar r ay u t i l . swap( elementi , j−c [ j ]+s , j−q+s ) ;c [ j ]=q ;f l a g=fa l se ;

} else{i f ( q==j+1)s++;i f (q<0 | | q==j +1){

d [ j ]=−d [ j ] ;j−−;

}}

}while ( f l a g ) ;}while ( true ) ;

}

5

4 Determinare una specifica permutazione dall’insieme delle permuta-zioni

Potrebbe essere necessario determinare una singola permutazione dall’insieme delle per-mutazioni ordinate e inutile determinarle tutte.

In questo caso si deve evitare di generare tutte le permutazioni fino a quella cercata in-quanto si vuole determinare una specifica permutazione in tempo costante o quantomenoproporzionale al numero di elementi del dominio.

La soluzione risiede nell’uso dei factoradic

4.1 I Factoradic

Di solito un numero viene rappresentato come un polinomio di potenze della base

1936 = 1 · 103 + 9 · 102 + 3 · 101 + 6 · 100

inquanto le potenze dei primi n numeri costituiscono una base che permette di rappre-sentare univocamente un numero con un polinomio.

Anche i fattoriali dei primi n numeri costituiscono una base , quindi e possibilerappresentare univocamente un numero come polinomio dei fattoriali della base

1936 = 2 · 6! + 4 · 5! + 0 · 4! + 2 · 3! + 2 · 2! + 0 · 1!

questa rappresentazione e detta factoradic. L’univocita di questa rappresentazione egarantita dal fatto che la somma dei primi n fattoriali moltiplicati per il loro indice esempre il fattoriale successivo meno 1.

n∑

i=0

i · i! = (n + 1)! − 1

caratteristica fondamentale dei factoradic e il costistuire un codice che permette di as-sociare al numero n rappresentato la n-esima permutazione dell’insieme degli elementidella base, questo “codice di traduzione” viene chiamato codice di Lehmer

4.2 Interpretazione dei codici di Lehmer, generazione della permutazione associata

Dal factoradic si puo ottenere la permutazione invertendo i singoli elementi o i segmentidella permutazione di base [1,2,3,4] con gli elementi a destra usando l’elemento del codicedi Lehmer come lunghezza del segmento da spostare.

Per esempio

� il codice 0110 indica che, partendo dalla permutazione di base, si deve invertirel’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 indicaquesto: due elementi di uno e NON un elemento di due) ottenendo [1,4,2,3]

6

n Factoradic Permutazione Permutazione Vettore degli Vettore delle(lessicografica) (plain changes) scambi direzioni

0 0000 [ 1,2,3,4 ] [ 1,2,3,4 ] [ 0,0,0,0 ] ----

1 0010 [ 1,2,4,3 ] [ 1,2,4,3 ] [ 0,0,0,1 ] ----

2 0100 [ 1,3,2,4 ] [ 1,4,2,3 ] [ 0,0,0,2 ] ----

3 0110 [ 1,3,4,2 ] [ 4,1,2,3 ] [ 0,0,0,3 ] ----

4 0200 [ 1,4,2,3 ] [ 4,1,3,2 ] [ 0,0,1,3 ] +---

5 0210 [ 1,4,3,2 ] [ 1,4,3,2 ] [ 0,0,1,2 ] -+--

6 1000 [ 2,1,3,4 ] [ 1,3,4,2 ] [ 0,0,1,1 ] --+-

7 1010 [ 2,1,4,3 ] [ 1,3,2,4 ] [ 0,0,1,0 ] ---+

8 1100 [ 2,3,1,4 ] [ 3,1,2,4 ] [ 0,0,2,0 ] ----

9 1110 [ 2,3,4,1 ] [ 3,1,4,2 ] [ 0,0,2,1 ] ----

10 1200 [ 2,4,1,3 ] [ 3,4,1,2 ] [ 0,0,2,2 ] ----

11 1210 [ 2,4,3,1 ] [ 4,3,1,2 ] [ 0,0,2,3 ] ----

12 2000 [ 3,1,2,4 ] [ 4,3,2,1 ] [ 0,1,2,3 ] ++--

13 2010 [ 3,1,4,2 ] [ 3,4,2,1 ] [ 0,1,2,2 ] ++--

14 2100 [ 3,2,1,4 ] [ 3,2,4,1 ] [ 0,1,2,1 ] +-+-

15 2110 [ 3,2,4,1 ] [ 3,2,1,4 ] [ 0,1,2,0 ] +--+

16 2200 [ 3,4,1,2 ] [ 2,3,1,4 ] [ 0,1,1,0 ] -+--

17 2210 [ 3,4,2,1 ] [ 2,3,4,1 ] [ 0,1,1,1 ] -+--

18 3000 [ 4,1,2,3 ] [ 2,4,3,1 ] [ 0,1,1,2 ] --+-

19 3010 [ 4,1,3,2 ] [ 4,2,3,1 ] [ 0,1,1,3 ] --+-

20 3100 [ 4,2,1,3 ] [ 4,2,1,3 ] [ 0,1,0,3 ] +--+

21 3110 [ 4,2,3,1 ] [ 2,4,1,3 ] [ 0,1,0,2 ] -+-+

22 3200 [ 4,3,1,2 ] [ 2,1,4,3 ] [ 0,1,0,1 ] --++

23 3210 [ 4,3,2,1 ] [ 2,1,3,4 ] [ 0,1,0,0 ] --++

Tabella 2: Permutazioni di un insieme di 4 elementi secondo i vari algoritmi descritti

7

4.2.1 Algoritmi per la generazione di un Factoradic e della permutazione associata

l’algoritmo di generazione e molto semplice: le singole componenti vengono calcolate conl’operatore modulo

E’ lo stesso tipo di algoritmo che si usa per convertire un numero decimale in una basediversa, si va dividendo il numero per la base e i resti delle divisioni vanno a costituire ilnumero nella base di arrivo, solo che in questo caso la base non e costante ma decresce.

Listing 4: Algoritmo per la generazione di un Factoradic

public static int [ ] f a c t o r a d i c ( int numero , int base ){a s s e r t ( 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 ;

}

Listing 5: Dal Factoradic alla permutazione

public int [ ] permutazione ( int n){int [ ] lehmer=MyMath. f a c t o r a d i c (n , l en ) ;int a ;// creo l a permutazione d i basefor ( a = 0 ; a < l en ; a++)e lement i [ a ] = a + 1 ;// app l i c o i l cod icefor ( a = 0 ; a < l en ; a++){

i f ( lehmer [ a]==1)// caso banale , mi l im i t o a f a r e uno swapswap(a , a+1);

else i f ( lehmer [ a ]>1){// caso gener ico , spos t o un segmentoint k=lehmer [ a]+a ;int bu f f e r=e lement i [ k ] ;while (k>a ){

swap(k−1,k ) ;k−−;

}e lement i [ a]= bu f f e r ;

}}return e lement i ;

}

8

4.3 Generazione di permutazioni casuali con i factoradic

Dando come input alla funzione precedente un numero casuale compreso nel numero dipermutazioni si ottiene ovviamente una permutazione casuale.

5 Ricavare il numero di una permutazione (ranking)

I singoli termini del codice di Lehmer si possono anche interpretare come il numero dielementi che si trovano “al posto sbagliato”, cioe il numero di elementi minori dell’ele-mento preso in esame che si trovano alla sua destra (e che quindi violano l’ordinamentocrescente degli elementi).

Applicando questo teorema e possibile ricavare il codice di Lehmer di una permuta-zione e dal codice ricavare la posizione della permutazione.

I singoli elementi del codice di Lehmer sono costituiti dal numero di elementi minoridell’elemento che si trovano alla sua destra

Listing 6: Generazione del codice di Lehmer

public static int [ ] inverseLehmer ( int [ ] v ){int n=v . l ength ;int [ ] lh=new int [ n ] ;lh [ n−1]=0;for ( int a=0; a<n−1; ++a ){

int i = 0 ;for ( int b=a ; b<n ; ++b)

i f ( v [ b]<v [ a ] ) i++;lh [ a ] = i ;

}return lh ;

}

Listing 7: Calcolo della posizione della permutazione

public static int rank ( int [ ] permutazione ){int [ ] l=inverseLehmer ( permutazione ) ;int f =1;int r=0;int n=permutazione . l ength ;for ( int a=1;a<(n+1);a++){

r=r+f � l [ n−a ] ;f=f �a ;

}return r ;

}4

4articolo originale in http://thedarshan.wordpress.com/2009/09/19/determinare-una-specifica-permutazione-dallinsieme-delle-permutazioni/ e http://wp.me/p9RRM-5l

9

6 Generare permutazioni casuali (algoritmo di Fisher-Yates o Knuthshuffle)

Originariamente sviluppato come algoritmo da eseguire “a mano” da Fisher e Yates nel1938 venne adattato all’uso automatico da Richard Durstenfeld nel 1964 e reso famosoda Donald E. Knuth anche se probabilmente questi ultimi lo ricrearono da zero vista lasua semplicita.

L’algoritmo opera semplicemente scorrendo il vettore e scambiando gli elementi conun altro elemento il cui indice e scelto casualmente. Se la scelta dei numeri casuali ecorretta ogni permutazione ha la stessa probabilita di essere generata.

Listing 8: Shuffling

public static int [ ] s h u f f l e ( int [ ] e l ement i ){Random r = new Random ( ) ;int k , n ;for (n = e lement i . length −1; n >= 0 ; n−−){

k = r . next Int (n+1);Ar r a y u t i l . swap( elementi , k , n ) ;

}return e lement i ;

}

6.1 Problemi di bias

I modo piu comune di provocare una scelta errata dei numeri casuali e l’uso dell’operatoremodulo, per esempio in C si potrebbe ingenuamente generare il numero casuale conk = rand() % (n+1); questa implementazione non genera bias apprezabili per numeripiccoli di n ma potrebbe generarne per numeri di n paragonabili all massimo numerocasuale generabile (definito in C come RAND_MAX).

Per capire perche il modulo puo provocare bias supponiamo di dover generare unnumero casuale minore di 16 disponendo di un generatore di numeri casuali interi da 0 a99. generando il numero come k = rand() % 16; l’operatore modulo divide il numerogenerato dalla funzione rand() per 17 e ne restituisce il resto.

100 e 16 non sono divisibili, 10016 = 6.25 il primo numero divisibile per 100 successivo

al 16 e il 20, quindi i numeri da 0 a 3 avranno piu possibilita di essere generati inparticolare il bias di questi numeri sara 1

100/17 = 0.17 cioe il 17%Kerninghan e Ritchie nel loro The C Programming Language suggeriscono di definire

la macro

#define frand() ((double) rand() / (RAND_MAX+1.0))

ma nemmeno questo metodo e perfetto ,anche se la generazione attraverso i float generaun bias minore e non distribuito tra i primi numeri un certo bias e comunque presente.

10

L’unico modo per evitare il bias e adattare generatore a generare numeri nel rangecorretto, questa soluzione e implementata in Java che usa il generatore di Lehmer.

La descrizione dei generatori di numeri casuali in ogni caso non e lo scopo di questoarticolo, per ulteriori approfondimenti sul generatore di Lehmer rimando al solito testodi Knuth 5

5 Donald E. Knuth The Art of Computer Programming, Volume 2: Seminumerical Algorithms, section3.2.1.

11