Permutations Circulaires

Une permutation circulaire est un arrangement de $ n $ éléments autour d'un cercle, dans lequel il n'existe pas de position de départ privilégiée. Deux arrangements sont considérés comme identiques si l'un peut être obtenu à partir de l'autre par une rotation du cercle.

Mathématiquement, les permutations circulaires correspondent aux classes d'équivalence des permutations linéaires sous l'action du groupe cyclique $ C_n $

Une permutation classique (linéaire) possède une position de départ et une position de fin. Dans une permutation circulaire, aucune position de départ n'est privilégiée.

Pour visualiser cette différence, imaginer une ronde : couper la ronde à différents endroits produit plusieurs listes linéaires différentes, mais une seule disposition circulaire.

Pour $ n $ éléments distincts, le nombre de permutations circulaires est : $ (n-1)! $

En effet, en fixant arbitrairement un élément, il est possible de permuter les $ n-1 $ éléments restants. Il existe donc $ (n-1)! $ arrangements.

Pour des éléments distincts, il est possible de choisir un point de départ pour chaque classe de rotations.

1 - fixer un élément

2 - générer toutes les permutations des $ n-1 $ éléments restants par backtracking

3 - ajouter l'élément fixe au début de chaque permutation générée

Chaque permutation obtenue représente alors une permutation circulaire différente, sans doublon.

Les permutations circulaires apparaissent dans de nombreux problèmes où aucune position de départ n'est privilégiée.

— placement d'invités autour d'une table ronde

— organisation de séquences ou de motifs cycliques

— dénombrement de colliers de perles ou d'objets colorés

— étude de séquences biologiques circulaires (certains génomes bactériens)

— problèmes combinatoires impliquant des cycles ou des configurations périodiques