Trouver la n-ième permutation sans calculer les autres

Voici une solution qui vous permet de sélectionner la taille de la permutation. Par exemple, en plus d'être en mesure de générer toutes les permutations de 10 éléments, il peut générer des permutations de paires parmi 10 éléments. Aussi, il permute les listes d'objets arbitraires, et pas seulement les nombres entiers.

function nth_permutation($atoms, $index, $size) {
    for ($i = 0; $i < $size; $i++) {
        $item = $index % count($atoms);
        $index = floor($index / count($atoms));
        $result[] = $atoms[$item];
        array_splice($atoms, $item, 1);
    }
    return $result;
}

Exemple d'utilisation:

for ($i = 0; $i < 6; $i++) {
    print_r(nth_permutation(['A', 'B', 'C'], $i, 2));
}
//=> AB, BA, CA, AC, BC, CB

---

Comment ça fonctionne?

Il y a une idée très intéressante derrière elle. Prenons la liste A, B, C, D. Nous pouvons construire une permutation par les éléments de dessin de lui comme d'un jeu de cartes. D'abord, nous pouvons tirer de l'un des quatre éléments. Puis l'un des trois éléments restants, et ainsi de suite, jusqu'à ce que finalement nous n'avons plus rien.

Ici est une séquence de choix. En commençant par le haut, nous passons à la troisième voie, la première, la seconde et la première. Et c'est notre permutation #13.

Penser à la façon, compte tenu de cette séquence de choix, vous devriez obtenir le nombre treize algorithmiquement. Faites l'inverse de l'algorithme, et c'est la façon dont vous pouvez reconstituer la séquence à partir d'un entier.

Nous allons essayer de trouver un schéma général pour l'emballage d'une séquence de choix dans un entier sans redondance, et le déballage de retour.

Un intéressant modèle est appelé nombre décimal du système. "27" peut être considéré comme le choix de chemin #2 sur 10, puis en choisissant le chemin n ° 7 sur 10.

Mais chaque chiffre ne peut encoder des choix à partir de 10 alternatives. D'autres systèmes qui ont un fixe radix, comme binaire et hexadécimal, aussi ne peut encoder des séquences de choix d'un nombre fixe de solutions de rechange. Nous voulons un système avec une variable radix, un peu comme les unités de temps, "14:05:29" 14 heures à partir de 24, 5 minutes à partir de 60, deuxième 29 à partir de la 60.

Que si nous prenons le générique de nombre en chaîne et chaîne-nombre de fonctions, et de les tromper en utilisant une combinaison de radixes? Au lieu de prendre une seule radix, comme parseInt('boeuf', 16) et (48879).toString(16), ils vont prendre un radix pour chaque chiffre.

function pack(digits, radixes) {
    var n = 0;
    for (var i = 0; i < digits.length; i++) {
        n = n * radixes[i] + digits[i];
    }
    return n;
}

function unpack(n, radixes) {
    var digits = [];
    for (var i = radixes.length - 1; i >= 0; i--) {
        digits.unshift(n % radixes[i]);
        n = Math.floor(n / radixes[i]);
    }
    return digits;
}

Est-ce que même travail?

//Decimal system
pack([4, 2], [10, 10]); //=> 42

//Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]); //=> 42

//Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]); //=> 42

Et maintenant à l'envers:

unpack(42, [10, 10]); //=> [4, 2]

unpack(42, [5, 4, 3, 2, 1]); //=> [1, 3, 0, 0, 0]

C'est tellement beau. Maintenant, nous allons appliquer ce paramétrique système de nombre de le problème des permutations. Nous allons envisager de longueur 2 permutations de A, B, C, D. Quel est le nombre total d'entre eux? Voyons voir: tout d'abord, nous attirons l'un des 4 éléments, l'un des 3 autres, c'est 4 * 3 = 12 manières de rédiger 2 articles. Ces 12 façons peuvent être emballés en nombres entiers [0..11]. Donc, imaginons que nous avons emballé déjà, et de tenter de le décompresser:

for (var i = 0; i < 12; i++) {
    console.log(unpack(i, [4, 3]));
}

//[0, 0], [0, 1], [0, 2],
//[1, 0], [1, 1], [1, 2],
//[2, 0], [2, 1], [2, 2],
//[3, 0], [3, 1], [3, 2]

Ces chiffres représentent des choix, pas d'index dans le tableau d'origine. [0, 0] ne veut pas dire prendre A, A, cela signifie la prise de l'élément de #0 à partir de A, B, C, D (c'est Un), puis l'élément de #0 à partir du reste de la liste B, C, D (c'est B). Et la permutation est A, B.

Un autre exemple: [3, 2] signifie la prise de l'élément n ° 3 de A, B, C, D (c'est D) et le point n ° 2 de la le reste de la liste A, B, C (c'est C). Et la permutation est D, C.

Cette cartographie est appelé Lehmer code. Nous allons carte tous ces Lehmer codes de permutations:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

C'est exactement ce dont nous avons besoin. Mais si vous regardez la unpack fonction, vous remarquerez qu'il produit des chiffres de droite à gauche (à l'inverse les actions de pack). Le choix de 3 sera décompressé avant le choix de 4. C'est malheureux, parce que nous voulons choisir une des 4 éléments avant de choisir à partir de 3. Sans être en mesure de le faire, nous devons calculer la Lehmer le premier code, l'accumuler dans un tableau temporaire, puis de l'appliquer sur le tableau d'éléments pour calculer l'effectif de permutation.

Mais si nous ne nous soucions pas de l'ordre lexicographique, nous pouvons prétendre que nous voulons choisir à partir de 3 éléments avant de choisir à partir de 4. Ensuite, le choix de 4 sortira de unpack premier. En d'autres termes, nous allons utiliser unpack(n, [3, 4]) au lieu de unpack(n, [4, 3]). Cette astuce permet de calculer le chiffre suivant du code de Lehmer et les appliquer immédiatement à la liste. Et c'est exactement comment nth_permutation() œuvres.

Une dernière chose que je veux mentionner, c'est que unpack(i, [4, 3]) est étroitement liée à la factorielle du nombre de système. Regarder que le premier arbre de nouveau, si nous voulons que les permutations de taille 2 sans doublons, il nous suffit de passer chaque seconde permutation de l'index. Qui va nous donner 12 permutations de longueur 4, qui peut être coupé à la longueur 2.

for (var i = 0; i < 12; i++) {
    var lehmer = unpack(i * 2, [4, 3, 2, 1]); //Factorial number system
    console.log(lehmer.slice(0, 2));
}

Voici un algorithme pour convertir entre des permutations et des rangs dans le temps linéaire. Toutefois, le classement qu'il utilise n'est pas lexicographique. C'est bizarre, mais cohérente. Je vais donner deux fonctions, l'une qui se convertit en un rang à une permutation, et celui qui fait l'inverse.

D'abord, à unrank (aller à partir du rang de permutation)

Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]

unrank(n, r, p)
  if n > 0 then
    swap(p[n-1], p[r mod n])
    unrank(n-1, floor(r/n), p)
  fi
end

Prochain, à rang:

Initialize:
p = input permutation
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)
n = length(p)

rank(n, p, q)
  if n=1 then return 0 fi
  s = p[n-1]
  swap(p[n-1], p[q[n-1]])
  swap(q[s], q[n-1])
  return s + n * rank(n-1, p, q)
end

Le temps d'exécution de ces deux est O(n).

Il y a un beau, lisible papier expliquant pourquoi cela fonctionne: Classement & Unranking Permutations dans le Temps Linéaire, par Myrvold & Ruskey, Traitement de l'Information Lettres, Volume 79, Numéro 6, 30 septembre 2001, Pages 281-284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Le code suivant calcule la kième permutation de n.

je.e n=3.
Les différentes permutations sont
123
132
213
231
312
321

Si k=5, retour 312.
En d'autres termes, il donne la kième vocabulaire de la permutation.

    public static String getPermutation(int n, int k) {
char temp[] = IntStream.range(1, n + 1).mapToObj(i -> "" + i).collect(Collectors.joining()).toCharArray();
return getPermutationUTIL(temp, k, 0);
}
private static String getPermutationUTIL(char temp[], int k, int start) {
if (k == 1)
return new String(temp);
int p = factorial(temp.length - start - 1);
int q = (int) Math.floor(k / p);
if (k % p == 0)
q = q - 1;
if (p <= k) {
char a = temp[start + q];
for (int j = start + q; j > start; j--)
temp[j] = temp[j - 1];
temp[start] = a;
}
return k - p >= 0 ? getPermutationUTIL(temp, k - (q * p), start + 1) : getPermutationUTIL(temp, k, start + 1);
}
private static void swap(char[] arr, int j, int i) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int factorial(int n) {
return n == 0 ? 1 : (n * factorial(n - 1));
}

Si vous stockez toutes les permutations dans la mémoire, par exemple dans un tableau, vous devriez être en mesure de ramener un à un, en O(1) fois.

Cela signifie que vous avez à stocker toutes les permutations, de sorte que si le calcul de toutes les permutations prend beaucoup de temps, ou de les stocker prend un trop grand espace, alors ce ne peut être une solution.

Ma suggestion serait d'essayer quand même, et de revenir si il est trop gros/lente, il n'y a aucun point de la recherche d'un "sage" solution si un naïf va faire le travail.