Comment ce « algorithme de génération de commande Lexographic » fonctionne?

Question

Wikipedia :

génération d'ordre alphabétique

  

Pour tout nombre k, avec 0 ≤ k

function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j);
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- j);
     }
     return s;
 }

Quelle est la logique derrière tout cela? Comment ça marche ??

Answer 1

Imaginez que vous avez un nombre entier x et vous voulez savoir quel chiffre est en position de centaines. (Si x = Par ex 4723 vous voulez la réponse 7.) Pour calculer cela, vous devez d'abord diviser par 100, jeter la partie décimale. (Dans notre exemple, cela laisse 47.) Ensuite, trouver le reste quand on divise par 10.

Maintenant, supposons que vous voulez trouver la valeur du chiffre dans la position des milliers. Pour trouver que vous aviez d'abord diviser par 1000, jeter la partie décimale, puis retrouver le reste quand on divise par 10.

Dans le système régulier de numérotation décimale, chaque lieu possède l'une des 10 valeurs. Vous pouvez constater que dans notre exercice de chiffres d'enquête nous avons d'abord diviser par le nombre de combinaisons possibles de valeurs dans des endroits à droite de celui que nous préoccupons (10 * 10 dans le premier exemple). Ensuite, nous trouvons le reste en divisant par le nombre de valeurs possibles pour l'endroit où nous soucions. Bien sûr, tous endroits ont 10 valeurs possibles, donc nous venons de diviser par 10.

maintenant , imaginez un système de numérotation où chaque lieu est titulaire d'un nombre différent de valeurs. Notre droit plus lieu peut avoir deux valeurs, 0 ou 1. Le prochain lieu peut avoir trois valeurs, 0, 1 ou 2; etc. Dans ce système, on compte comme ceci:

  0
  1
 10
 11
 20
 21
100
101
110
111
120
121
200
201
210
211
220
...

est ce que wrang-wrang signifie par un "numéro de base variable".

Maintenant, vous pouvez voir comment on calcule le chiffre dans un endroit dans ce système. Pour trouver le plus à droite, nous ne devons diviser d'abord, et on trouve le reste modulo 2, parce qu'il ya 2 valeurs possibles pour un chiffre dans cette colonne. Pour trouver la colonne suivante à gauche, nous avons d'abord diviser par le nombre de combinaisons possibles pour les chiffres dans les colonnes de droite: il n'y a qu'une seule colonne avec deux chiffres possibles, donc on divise par 2. Ensuite, nous prenons le modulo 3 reste, parce qu'il ya trois valeurs possibles pour cette colonne. Continuant à gauche, pour la 3ème colonne on divise par 6 (parce que les colonnes à droite ont 3 et 2 possibilités chacun, multipliant pour faire 6), puis prendre le modulo reste 4, parce qu'il ya 4 valeurs possibles dans cette colonne.

Jetons un coup d'oeil à la fonction:

function permutation(k, s) {
    var int n:= length(s); factorial:= 1;
    for j= 2 to n- 1 {             // compute (n- 1)!
        factorial:= factorial* j;
    }

factorial commence comme (n-1)!

    for j= 1 to n- 1 {

Chaque fois que nous obtenons ici, factorial est égal à (n-j)! Cela est évident la première fois autour, depuis j = 1 et nous savons que nous initialisions factorial à (n-1)! Nous verrons plus tard que factorial est en effet toujours (n-j)!

        tempj:= (k/ factorial) mod (n+ 1- j);

on divise ici k par factorial (qui est égal à (n-j)!) Et jeter le reste, nous prenons le restâmes quand on divise le résultat par (n + 1-j). Attendez une minute, tout ce que je babille commencé avec commence à sembler familier! Nous constatons que la valeur du « chiffre » dans la nième colonne de gauche en utilisant notre « numéro base variable système »!

Ce bit suivant prend la séquence d'éléments entre les indices j et j + tempj et le fait tourner vers la droite - à-dire chaque élément se déplace jusqu'à une index, sauf le dernier, qui se déplace en arrière vers le début. Il est important de se rendre compte que tous les chiffres à droite de position j sont en ordre. Nous sommes effectivement plumer un d'entre eux et en poussant le reste le long de les garder dans l'ordre. Lequel nous arrachera dépend de tempj. Lorsque tempj est 0, nous sélectionnons les plus petits (et en fait ne pas besoin de faire tout coup de coude), lorsque tempj est égal à n-j, on choisit le plus grand.

        temps:= s[j+ tempj]
        for i= j+ tempj to j+ 1 step -1 {
            s[i]:= s[i- 1];      // shift the chain right
        }
        s[j]:= temps;

Ensuite, (n-j)! divisé par (n-j) donne (n-j-1)! Si vous y pensez, vous devriez voir que cela signifie que lorsque nous reviendrons au sommet de la boucle et j a augmenté d'une, factorial sera de nouveau égale (n-j)!

        factorial:= factorial/ (n- j);
    }
    return s;
}

J'espère que cela aide un peu!

Answer 2

Pensez à un tableau multidimensionnel, de toutes les permutations de n éléments, dont les dimensions:

p[n][n-1][n-2]...[1]

Tout tableau multidimensionnel peut être linéarisé dans un tableau 1D de dimension:

a[n*(n-1)*(n-2)*...*1]

Il est comme un numéro de base variable; aller dans l'ordre de valeur numérique ne vous donne l'ordre lexicographique sur les chiffres.

L'index que vous utilisez pour faire référence à un x tuple [n] = par exemple (i[n],i[n-1]...,i[0]) est sum_j i[j]*(j!)

Ainsi, la division / mod récupère la position suivante du tuple.

La valeur de l'indice kième dans le tuple est le produit des dimensions à son droit, ce qui arrive à k!.

Answer 3

Dis u ont la séquence initiale en tant que [] = {1,2,3,4,5,6} de n = 6; et u veulent générer perm kième. Avec 1 sur la place Ist, u peut générer 5! (À savoir (n-1)!) Perms avec les places restantes.

1 ,.......  

Alors u Xchange 1 et 2 et encore u peut à nouveau générer 5! perms.

2 ,.......

L'idée est donnée k, nous devons trouver la mesure de k. Ce que je veux dire est: dire k est de 225, combien de 5! k n'ont: 245/5! = 2 Donc, si k = 245, dans la permutation que je veux générer, d'abord est sans aucun doute 3 (à savoir un [2]) (bcoz après avoir 2 * 5! = 240, je XCHANGE 1 et 3), j'aurai

3,1,2,4,5,6 (the array a[] obtained after shifting the chain)
(why we are shifting is to make the remaining array sorted for the 
  next iteration so that lexicographic order is maintained.)

c'est pourquoi dans le algo, u ne k / (n-1)! dans la première itération. Et obtenir reste k = k mod (n-1) !. Ceci est une nouvelle valeur de k et u aller faire récursive la même chose avec (n-j)! sur les places restantes.