® Le plus petit entier r > 0 tel que s
r = id E est le ppcm des longueurs des cycles c 1 ,. . .,c m .
Comme les supports des cycles c i sont des parties deux à deux disjointes, on peut
composer ces cycles dans l’ordre qu’on veut (proposition page 72).
Il s’ensuit que l’on a s
k = c
k
1 c
k
2 · · · c
k
m pour tout entier k.
Démonstration. Les éléments de E se répartissent en les parties C 1 = iter(a 1 ), C 2 =
iter(a 2 ), . . . , C m = iter(a m ) deux à deux disjointes. Quand on itère s, tous les éléments de C k
décrivent un même cycle c k de support C k . Soit x ∈ C k . On a donc c k (x) = s(x) et c k (x) ∈ C k .
Pour tout j = k, ni x, ni c k (x) n’appartiennent à C j , donc c j (x) = x et c j c k (x) = c k (x). Il
vient donc c 1 c 2 · · · c m (x) = c k (x) = s(x). Cette égalité étant vraie pour tout x ∈ C k et pour
tout k, elle est vraie quel que soit x ∈ E .
Si x est un élément de C k , il revient au même d’itérer x par s ou par c k , donc s
r (x) = c
r
k (x)
pour tout entier r. Pour que l’on ait s
r (x) = x quel que soit x ∈ C k , il faut et il suffit que r soit
multiple de la longueur de c k . Pour que l’on ait s
r (x) = x quel que soit x ∈ E , une condition
nécessaire et suffisante est donc que r soit multiple du ppcm des longueurs des cycles c k .
Exemple. La permutation s de l’exemple précédent se décompose en trois cycles : le
4-cycle (1 3 8 7), le 3-cycle (2 6 4) et le 2-cycle (9 10). On a s = (1 3 8 7)(2 6 4)(9 10).
Le plus petit entier r tel que s
r = id est r = ppcm(4, 3, 2) = 12.
Algorithme de décomposition en cycles
Soit s une permutation de {1, 2, . . . , n}. On suppose s différent de l’identité. L’algorithme suivant produit la liste L des cycles composant s. Un cycle (a 0 a 1 · · · a p )
est représenté par la liste [a 0 , . . . , a p ]. On commence par chercher le cycle décrit par
les itérés de 1 en marquant chacun des entiers obtenus ; puis on cherche les itérés
du plus petit entier non marqué et l’on continue ainsi jusqu’à ce que tous les entiers
soient marqués. On calcule chaque fois le nombre d’itérés, car si l’on trouve un
point fixe de s, on le supprime puisqu’il ne produit pas de cycle.
initialisations : (L, C ← listes vides) (m[i] = 0 pour tout i tel que 1 i n)
les entiers marqués seront les entiers i tels que m(i) = 1.
a) u ← min{i | 1 i n et m[i] = 0} ;
b) C ← C, u (on ajoute u à la liste C ) ; m[u] ← 1 ; ← 1 ; v ← s(u) ;
c) tant que v = u :
C ← C, v (on ajoute v à la liste C ) ; m[v] ← 1 ; ← + 1 ; v ← s(v) ;
d) si 2, L ← L, C (on ajoute la liste C à la liste L) ;
e) aller en a).
À la fin de l’algorithme, on obtient une liste L de listes C 1 , C 2 , . . . La permutation
s est la composée des cycles représentés par les listes C i .
74 – PERMUTATIONS
r = id E est le ppcm des longueurs des cycles c 1 ,. . .,c m .
Comme les supports des cycles c i sont des parties deux à deux disjointes, on peut
composer ces cycles dans l’ordre qu’on veut (proposition page 72).
Il s’ensuit que l’on a s
k = c
k
1 c
k
2 · · · c
k
m pour tout entier k.
Démonstration. Les éléments de E se répartissent en les parties C 1 = iter(a 1 ), C 2 =
iter(a 2 ), . . . , C m = iter(a m ) deux à deux disjointes. Quand on itère s, tous les éléments de C k
décrivent un même cycle c k de support C k . Soit x ∈ C k . On a donc c k (x) = s(x) et c k (x) ∈ C k .
Pour tout j = k, ni x, ni c k (x) n’appartiennent à C j , donc c j (x) = x et c j c k (x) = c k (x). Il
vient donc c 1 c 2 · · · c m (x) = c k (x) = s(x). Cette égalité étant vraie pour tout x ∈ C k et pour
tout k, elle est vraie quel que soit x ∈ E .
Si x est un élément de C k , il revient au même d’itérer x par s ou par c k , donc s
r (x) = c
r
k (x)
pour tout entier r. Pour que l’on ait s
r (x) = x quel que soit x ∈ C k , il faut et il suffit que r soit
multiple de la longueur de c k . Pour que l’on ait s
r (x) = x quel que soit x ∈ E , une condition
nécessaire et suffisante est donc que r soit multiple du ppcm des longueurs des cycles c k .
Exemple. La permutation s de l’exemple précédent se décompose en trois cycles : le
4-cycle (1 3 8 7), le 3-cycle (2 6 4) et le 2-cycle (9 10). On a s = (1 3 8 7)(2 6 4)(9 10).
Le plus petit entier r tel que s
r = id est r = ppcm(4, 3, 2) = 12.
Algorithme de décomposition en cycles
Soit s une permutation de {1, 2, . . . , n}. On suppose s différent de l’identité. L’algorithme suivant produit la liste L des cycles composant s. Un cycle (a 0 a 1 · · · a p )
est représenté par la liste [a 0 , . . . , a p ]. On commence par chercher le cycle décrit par
les itérés de 1 en marquant chacun des entiers obtenus ; puis on cherche les itérés
du plus petit entier non marqué et l’on continue ainsi jusqu’à ce que tous les entiers
soient marqués. On calcule chaque fois le nombre d’itérés, car si l’on trouve un
point fixe de s, on le supprime puisqu’il ne produit pas de cycle.
initialisations : (L, C ← listes vides) (m[i] = 0 pour tout i tel que 1 i n)
les entiers marqués seront les entiers i tels que m(i) = 1.
a) u ← min{i | 1 i n et m[i] = 0} ;
b) C ← C, u (on ajoute u à la liste C ) ; m[u] ← 1 ; ← 1 ; v ← s(u) ;
c) tant que v = u :
C ← C, v (on ajoute v à la liste C ) ; m[v] ← 1 ; ← + 1 ; v ← s(v) ;
d) si 2, L ← L, C (on ajoute la liste C à la liste L) ;
e) aller en a).
À la fin de l’algorithme, on obtient une liste L de listes C 1 , C 2 , . . . La permutation
s est la composée des cycles représentés par les listes C i .
74 – PERMUTATIONS