Nombre de swaps dans une permutation

Existe-t-il un algorithme efficace (efficace en termes de grande notation O) pour trouver le nombre de permutations permettant de convertir une permutation P en permutation d’identité I? Les échanges n’ont pas besoin d’être sur des éléments adjacents, mais sur des éléments quelconques.

Donc par exemple:

I = {0, 1, 2, 3, 4, 5}, number of swaps is 0 P = {0, 1, 5, 3, 4, 2}, number of swaps is 1 (2 and 5) P = {4, 1, 3, 5, 0, 2}, number of swaps is 3 (2 with 5, 3 with 5, 4 with 0)

Une idée est d’écrire un algorithme comme celui-ci:

 int count = 0; for(int i = 0; i < n; ++ i) { for(; P[i] != i; ++ count) { // could be permuted multiple times std::swap(P[P[i]], P[i]); // look where the number at hand should be } }

Mais il m’est pas très clair pour moi de savoir s’il est garanti que cela se termine ou si on trouve un nombre correct de swaps. Cela fonctionne sur les exemples ci-dessus. J’ai essayé de générer toutes les permutations sur 5 et 12 chiffres et il se termine toujours sur ceux-ci.

Ce problème se pose en algèbre linéaire numérique. Certaines décompositions masortingcielles utilisent le pivotement, qui permute les lignes avec la plus grande valeur pour la ligne suivante à manipuler, afin d’éviter les divisions par petits nombres et d’améliorer la stabilité numérique. Certaines décompositions, telles que la décomposition de LU, peuvent être utilisées ultérieurement pour calculer le déterminant de masortingce, mais le signe du déterminant de la décomposition est opposé à celui de la masortingce d’origine, si le nombre de permutations est impair.

EDIT : Je conviens que cette question est similaire à Compter les swaps adjacents nécessaires pour convertir une permutation en une autre . Mais je dirais que cette question est plus fondamentale. La conversion de permutation de l’une à l’autre peut être convertie en ce problème en inversant la permutation cible dans O (n), en composant les permutations dans O (n), puis en recherchant le nombre de permutations identitaires. Résoudre cette question en représentant explicitement l’identité comme une autre permutation semble sous-optimal. En outre, l’autre question comportait jusqu’à hier quatre réponses pour lesquelles une seule (apparemment par | \ / | ad) était apparemment utile, mais la description de la méthode semblait vague. Maintenant, l’utilisateur lizusek a répondu à ma question. Je ne suis pas d’accord avec la fermeture de cette question en double.

EDIT2 : L’algorithme proposé semble en fait plutôt optimal, comme indiqué dans un commentaire de l’utilisateur rcgldr, voir ma réponse à Compter les échanges adjacents nécessaires pour convertir une permutation en une autre .

Je crois que la clé est de penser à la permutation en termes de décomposition en cycle .

Ceci exprime toute permutation en tant que produit de cycles disjoints.

Les faits principaux sont:

L’échange d’éléments dans deux cycles disjoints produit un cycle plus long
L’échange d’éléments dans le même cycle produit un cycle de moins
Le nombre de permutations nécessaires est nc où c est le nombre de cycles dans la décomposition

Votre algorithme permute toujours les éléments dans le même cycle afin de compter correctement le nombre de permutations nécessaires.

Si vous le souhaitez, vous pouvez également le faire dans O (n) en calculant la décomposition de cycle et en renvoyant n moins le nombre de cycles trouvés.

Le calcul de la décomposition du cycle peut être effectué dans O (n) en commençant par le premier nœud et en suivant la permutation jusqu’au retour au début. Marquez tous les nœuds visités, puis recommencez au nœud non visité suivant.

Je crois que ce qui suit est vrai:

Si S(x[0], ..., x[n-1]) est le nombre minimal de swaps nécessaires pour convertir x en {0, 1, ..., n - 1} , alors:

Si x[n - 1] == n - 1 , alors S(x) == S(x[0],...,x[n-2]) (c’est-à-dire, coupe le dernier élément)
Si x[-1] != n - 1 , alors S(x) == S(x[0], ..., x[n-1], ..., x[i], ... x[n-2]) + 1 , où x[i] == n - 1 .
S({}) = 0 .

Ceci suggère un algorithme simple pour calculer S(x) qui s’exécute en temps O(n) :

 int num_swaps(int[] x, int n) { if (n == 0) { return 0; } else if (x[n - 1] == n - 1) { return num_swaps(x, n - 1); } else { int* i = std::find(x, x + n, n - 1); std::swap(*i, x[n - 1]) return num_swaps(x, n - 1) + 1; } }