Comment pouvons-nous trouver efficacement la n-ième permutation d'un ensemble ?

Algorithme efficace pour identifier la n-ième permutation

Étant donné un tableau d'éléments représentant une permutation, cette question explore la possibilité d'un algorithme qui calcule efficacement la nième permutation sans calculer toutes les précédentes ceux.

Décomposition par permutation factorielle

La solution exploite le concept de décomposition factoradique. En effectuant des divisions successives par factorielles, il décompose l'indice de permutation en une séquence de quotients. Cette séquence représente la permutation souhaitée.

Ajustement des quotients

Cependant, les quotients initiaux ne tiennent pas compte de l'impact des valeurs précédentes. Une étape d’ajustement est donc nécessaire. Pour chaque quotient, il incrémente la valeur du nombre de quotients précédents plus petits ou égaux.

Implémentation

Une implémentation C de l'algorithme est fournie ci-dessous :

void ithPermutation(const int n, int i) {
    int *fact = new int[n], *perm = new int[n];

    // Compute factorials
    fact[0] = 1;
    for (int k = 1; k < n; k++)
        fact[k] = fact[k - 1] * k;

    // Compute factorial code
    for (int k = 0; k < n; k++) {
        perm[k] = i / fact[n - 1 - k];
        i %= fact[n - 1 - k];
    }

    // Adjust values for permutation
    for (int k = n - 1; k > 0; k--)
        for (int j = k - 1; j >= 0; j--)
            if (perm[j] <= perm[k])
                perm[k]++;

    // Print permutation
    for (int k = 0; k < n; k++)
        cout << perm[k] << " ";
    cout << "\n";

    delete[] fact;
    delete[] perm;
}

Exemple

Par exemple, ithPermutation(10, 3628799) renvoie la dernière permutation de dix éléments :

9 8 7 6 5 4 3 2 1 0

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!