«

»

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.

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

1936=\mathbf{1}\cdot 10^{3}+\mathbf{9}\cdot 10^{2}+\mathbf{3}\cdot 10^{1}+\mathbf{6}\cdot 10^{0}

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

1936=\mathbf{2}\cdot 6! + \mathbf{4}\cdot 5! + \mathbf{0}\cdot 4! + \mathbf{2}\cdot 3! + \mathbf{2}\cdot 2!+ \mathbf{0}\cdot 1!

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.

\sum_{i=0}^{n} {i\cdot i!} = {(n+1)!} - 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

Share Button

3 comments

1 ping

  1. luca

    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

  2. thedarshan

    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.

  3. luca

    Una indicazione di come realizzare l’algoritmo inverso si trova comunque qui:
    http://en.wikipedia.org/wiki/Factoradic#Permutations

  1. Ricavare il numero di una permutazione (ranking) « The Darshan’s Weblog

    [...] 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 [...]

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

Puoi usare i seguenti tag ed attributi HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>