Comment pouvons-nous trouver directement la N-ième permutation d'un ensemble sans générer toutes les permutations précédentes ?

Obtenir directement la n-ième permutation

La tâche consiste à trouver la n-ième permutation d'un ensemble d'éléments sans explicitement tout calculer les permutations précédentes. Ceci peut être réalisé à l'aide d'un algorithme intelligent appelé algorithme factoradique.

L'algorithme factoradique exploite la décomposition factorielle de l'indice de permutation. En effectuant à plusieurs reprises une division euclidienne avec des nombres factoriels, nous obtenons un ensemble de quotients qui représentent la permutation.

Voici comment fonctionne l'algorithme :

1. Décomposition factorielle : Divisez l'indice de permutation n par la factorielle de (n-1) !, (n-2) !, et ainsi de suite. Les quotients sont stockés dans un tableau.
2. Représentation par permutation : Chaque quotient représente l'indice de l'élément choisi parmi les éléments restants.
3. Ajustement : Puisque les quotients ne tiennent pas compte des valeurs précédentes, ils doivent être ajustés pour refléter la permutation correcte. Incrémentez chaque quotient du nombre de quotients précédents qui lui sont inférieurs ou égaux.

Par exemple, trouvons la 3ème permutation de {'A', 'B', 'C'}.

• n = 3
• Quotients : [1, 0, 0]
• Quotients ajustés : [1, 0, 1]

La permutation est donc 'B', 'A', 'C', qui est bien la 3ème permutation de l'ensemble donné.

Le code C fourni implémente l'algorithme factoradique, démontrant comment obtenir le n-ième permutation directement sans calculer les précédentes.

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!