«

»

set 24

Ricavare 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 posizione di una specifica permutazione nell’insieme delle permutazioni ordinate lessicograficamente.

Ancora qualcosa sull’interpretazione dei codici di Lehmer

I singoli termini del codice di Lehmer si possono anche interpretare come il numero di elementi che si trovano “al posto sbagliato”, cioè il numero di elementi minori dell’elemento preso in esame che si trovano alla sua destra (e che quindi violano l’ordinamento crescente degli elementi).

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

Generazione del codice di Lehmer

“i singoli elementi del codice di Lehmer sono costituiti dal numero di elementi minori dell’elemento che si trovano alla sua destra”

    public static int[] inverseLehmer(int[] v){
        int n=v.length;
        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)
                if ( v[b]<v[a] ) i++;
            lh[a] = i;
        }
        return lh;
    }

Calcolo della posizione della permutazione (conversione da factoradic a numero)

    public static int rank(int[] permutazione){
        int[] l=inverseLehmer(permutazione);
        int f=1;
        int r=0;
        int n=permutazione.length;
        for(int a=1;a<(n+1);a++){
            r=r+f*l[n-a];
            f=f*a;
        }
        return r;
    }
Share Button