Définition

E désigne ici un ensemble fini à n éléments. On suppose n ≥ 2.
Soit f une permutation de E, et p un entier ≥ 2.
On dit que f est un "cycle d'ordre p" si on peut trouver dans E une suite d'éléments (x1,x2,...,xp) telle que: Au lieu de 'cycle' on dit aussi 'permutation circulaire'.
Les cycles ont un intérêt particulier en ce sens que ce sont des transformations assez simples, consistant à faire 'tourner' d'un cran une suite finie d'éléments.
En outre, ils servent de composants de base aux permutations, leurs puissances sont aisément calculables, et ils sont eux mêmes décomposables en permutations encore plus simples.
Avant de passer à la suite et pour prolonger la validité de certains énoncés, nous conviendrons de dire que les cycles d'ordre 0 ou 1 sont l'application identique.
Le premier résultat évident est le suivant:
Un cycle d'ordre p est d'ordre p au sens de la composition des permutations, c'est à dire que si f est un tel cycle fp=Id.

Voici quelques exemples de cycles et l'illustration du théorème ci-dessus:

Cliquez pour voir un cycle !
Cliquez pour voir ses puissances !

Décomposition en cycles

Théorème fondamental:

Si E est un ensemble fini à n éléments, toute permutation f se décompose en un produit de cycles.

Si tous les points de f sont fixes, il n'y a rien à démontrer. Sinon désignons par x1 un point non fixe, par x2 son image, par x3 l'image de x2 et ainsi de suite.
On fabrique ainsi une suite de points de E, et on note xp le premier élément de la suite tel que f(xp) ∈ {x1,...,xp-1}. Alors forcément f(xp)=x1, car dans le cas contraire, disons si f(xp)=xh avec h>1, alors xh aurait deux antécédents à savoir xp et xh-1, ce qui est impossible puisque f est une bijection.
Considérons maintenant le cycle g qui fait tourner les p points (x1,x2,...,xp).
Alors g-1of est une permutation sur un ensemble à n-p éléments, et il suffit donc d'appliquer l'hypothèse de récurrence.

Café Python

Voici un programme récursif qui décompose une permutation en cycles:

Voici maintenant un programme itératif utilisant les cycles pour générer toutes les permutations:


On travaille pour simplifier avec les n entiers: 0, 1, 2, ...,n-1
Pour permuter n'importe quoi il suffira d'utiliser un dictionnaire et de convertir chaque permutation.
Je suppose connu ce qu'est un cycle, et ses propriétés.
On considère d'abord le cycle C0 qui fait tourner les deux derniers entiers (n-2,n-1)
Puis le cycle C1 qui fait tourner les trois derniers (n-3,n-2,n-1)
Jusqu'au cycle C n-1 qui fait tourner tous les entiers.
Ensuite on procède comme cela:
On part de l'unique liste contenant la liste identique
Soit [[0,1,...,n-1]]
On applique à tous les éléments de la liste les deux permutations
C0 et C0*C0=Id, on obtient 2 éléments
[[0,1,...n-2,n-1][0,1,...,n-1,n-2]]
On applique à la nouvelle liste obtenue les trois permutations:
C1, C1*C1, C1*C1*C1=Id
On obtient une liste de 6 éléments, tous forcément distincts car le n-3 'circule'.
Et on itère le processus. On obtient à la fin n! permutations toutes distinctes, on les a donc toutes.
Cela revient à dire que le groupe symétrique d'ordre n est engendré par les n-1 cycles qui précèdent.