«

»

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

6 comments

1 ping

Vai al modulo dei commenti

  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

  4. Michele

    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

  5. Vincenzo La Spesa

    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.

  6. Vincenzo La Spesa

    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

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

Commenti disabilitati.