Maison >développement back-end >tutoriel php >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!