Comment obtenir directement le ème élément de la ème permutation d'une séquence (sans aucune récursivité)?

Vous pouvez trouver la n -ème permutation en faisant une division euclidienne répétée (quotient et reste, aka divmod) et en gardant une trace des lettres que vous choisissez. Vous pouvez ensuite choisir la i -ème lettre de cette permutation.

Soit S une copie de la chaîne initiale, L la longueur de cette chaîne et P le nombre de permutations ( L! ). T sera la n -ième permutation de S , construite étape par étape.
Exemple: S = "ABCD" , L = 4 et P = 24 . Prenons n = 15 pour l'exemple. T doit être "CBDA" à la fin.

Définissez P = P / L . Calculez divmod (n, P) , soit q le quotient ( n / P ) et r le reste ( n% P ). Retirez la q -ème lettre de S et ajoutez-la à T . Définissez n = r , décrémentez L et répétez jusqu'à L = 0 .
Exemple:
1) P = 24/4 = 6 , q = 15/6 = 2 , r = 15% 6 = 3 , S = "ABD" , T = "C" , n = r = 3 , L = 3 .
2) P = 6/3 = 2 , q = 3/2 = 1 , r = 3% 2 = 1 , S = "AD" , T = "CB" , n = r = 1 , L = 2 .
3) P = 2/2 = 1 , q = 1/1 = 1 , r = 1% 1 = 0 , S = "A" , T = "CBD" , n = r = 0 , L = 1 .
4) P = 1/1 = 1 , q = 0/1 = 0 , r = 0% 1 = 0 , S = "" , T = "CBDA" , n = r = 0 , L = 0 .

Puisque vous ne voulez que la i -ème lettre, vous pouvez vous arrêter chaque fois que la longueur de T est égale à i + 1 et prendre cette dernière lettre.

Je n'essaierai pas de coder ceci en Python car cela fait trop longtemps que je n'ai pas touché à Python, mais voici une démo en C ++ .

Désolé, pour mon Python. L'idée est que la lettre à toutes les positions se répète (number_of_pos - pos)! fois.

Par exemple. ABCD , la lettre à la première position se répéterait 3! fois. Donc, en divisant n par cette factorielle, nous avons maintenant quelle lettre est en première position. Pour trouver la lettre en deuxième position, nous devons supprimer cette lettre de l'ensemble (attribuez plutôt 0 ) et mettre à jour n avec n - n% 3! code> pour maintenant index de la lettre en deuxième position. Lors de l'application de cet index, nous devons faire attention à ne pas compter la lettre qui est en première position.

La complexité est O (kPosCount * kPosCount) .

#include <array>
#include <iostream>

const int kPosCount = 4;
const std::array<int, kPosCount> factorial = { 1,1,2,6 };
const std::array<int, kPosCount> kLetters = { 'A', 'B', 'C', 'D' };

char f(int pos, int n) {
    assert(pos < kPosCount);
    std::array<int, kPosCount> letters = kLetters;

    int res = 0;
    for (int i = 0; i <= pos; ++i) {
        const int letter = n / factorial[kPosCount - i - 1];
        int j = 0;
        for (int stillThere = 0; j < kPosCount; ++j) {
            if (letters[j] != 0) {
                if (stillThere == letter) {
                    break;
                }
                ++stillThere;
            }
        }
        letters[j] = 0;
        res = j;
        n %= factorial[kPosCount - i - 1];
    }
    return kLetters[res];
}

int main() {
    const int kMaxN = factorial.back() * kPosCount;
    for (int i = 0; i < kPosCount; ++i) {
        for (int j = 0; j < kMaxN; ++j) {
            std::cout << f(i, j) << " ";
        }
        std::cout << std::endl;
    }
}

Voici une version de votre fonction avec un ordre de permutation différent. Je n'ai pas forcé la taille de la permutation à 256 ici, vous devez donc la fournir comme premier argument.

>>> print('\n'.join(' '.join(str(elt_opt(4, k, i)) for i in range(4))
                    for k in range(factorial(4))))
0 3 2 1
0 3 1 2
0 1 3 2
0 1 2 3
0 2 3 1
0 2 1 3
1 0 2 3
1 0 3 2
1 3 0 2
1 3 2 0
1 2 0 3
1 2 3 0
2 0 3 1
2 0 1 3
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 2 1
3 0 1 2
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0

Cela a deux différences avec votre code.

Tout d'abord, les chiffres sont découpés de l'index de droite à gauche, ce qui signifie que les divmods bignum sont tous des divmods par un petit dividende. Je pensais que ce serait plus rapide que d'utiliser un dividende bignum, mais cela s'avère beaucoup plus lent. Cependant, cela évite d'avoir à précalculer les factorielles.

Deuxièmement, plutôt que de faire une série de pop s à partir du milieu d'une table, ce qui va être de complexité quadratique car l'opération pop est O (n), je échangez simplement chaque élément avec un élément avant. C'est beaucoup plus rapide, bien que l'arithmétique bignum domine le calcul.

En effet, elt (n, k, i) effectue les premières i étapes de un mélange Fisher-Yates de range (n) en utilisant la décomposition à base mixte de k comme quelles seraient les valeurs aléatoires dans un mélange aléatoire. Étant donné que le shuffle FY produit un résultat différent pour chaque séquence possible de valeurs aléatoires, et que la décomposition en base mixte de k produit une séquence différente pour chaque valeur différente de k , tous des permutations seront générées.

Voici à quoi ressemble l'ordre pour n = 4:

def elt_opt(n, k, i, fact=[1]):
    """Returns element i of permutation k from permutations of length n.
       Let the last argument default.
    """
    while len(fact) < n: fact.append(fact[-1]*len(fact))
    perm = list(range(n))
    for j in range(n-1, n-2-i, -1):
        r, k = divmod(k, fact[j])
        perm[j], perm[r] = perm[r], perm[j]
    return perm[n-i-1]

Pour accélérer réellement la fonction, j'ai réintroduit les factorielles précalculées (en tant que variable locale qui est prolongé si nécessaire). J'ai également micro-optimisé la boucle interne en supprimant autant d'arithmétique que possible, ce qui signifiait faire le mélange F-Y de l'arrière vers l'avant. Il en résulte un autre ordre de permutation; voir ci-dessous pour un exemple.

La fonction optimisée finale est environ 15% plus rapide que la version dans la question (c'est-à-dire qu'il faut environ 85% du temps pour faire un simple benchmark).

>>> print('\n'.join(' '.join(str(elt(4, k, i)) for i in range(4))
                    for k in range(factorial(4))))
0 1 2 3
1 0 2 3
2 1 0 3
3 1 2 0
0 2 1 3
1 2 0 3
2 0 1 3
3 2 1 0
0 3 2 1
1 3 2 0
2 3 0 1
3 0 2 1
0 1 3 2
1 0 3 2
2 1 3 0
3 1 0 2
0 2 3 1
1 2 3 0
2 0 3 1
3 2 0 1
0 3 1 2
1 3 0 2
2 3 1 0
3 0 1 2

Ordre de permutation:

def elt(n,k,i):
  """Returns element i of permutation k from permutations of length n"""
  perm = [*range(n)]
  for j in range(i+1):
    k, r = divmod(k, n-j)
    perm[j], perm[j+r] = perm[j+r], perm[j]
  return perm[i]