Permutations d’un ensemble fini
(Programmation avec Maple)
Préparation à la nouvelle épreuve d’informatique
de l’École Polytechnique.
Jean-Michel Ferrard
Avant-propos
Ce document vise a la préparation a la nouvelle épreuve d’informatique de l’École Polytechnique.
Les caractéristiques de cette épreuve peuvent être consultées à l’adresse :
http ://www.enseignement.polytechnique.fr/informatique/concours/
Parmi les langages de programmation possibles, on a choisi Maple, qui est le plus connu actuellement
des élèves de classe préparatoire n’ayant pas suivi l’option informatique.
Les concepteurs de l’épreuve recommandent de n’utiliser que des fonctionnalités de base, de façon à
travailler sur le plus petit dénominateur commun à tous les langages autorisés.
Dans ce document, on a scrupuleusement respecté ces consignes d’économie, même si c’est à regret.
On n’ignore pas que de nombreuses fonctionnalités de Maple permettent de réécrire complètement
certaines des fonctions ou procédures qui seront présentées dans ces pages.
Pour ne prendre qu’un exemple, la fonction identp de la question I-1 (et dont le rôle est de former
le tableau associé à la permutation identité de Sn) pourrait s’écrire :
identp:=(n::posint)->array([$1..n])
Le theme du présent document est l’étude du groupe symétrique Sn, c’est-a-dire l’ensemble des
bijections de En = {1, 2, . . . , n} dans lui-même.
On a inclus quelques rappels de cours, qui sont plus que des rappels pour la filiere PC* (ou le groupe
symétrique et la signature sont hors-programme) et dans certains cas pour la filière PSI* (en ce qui
concerne les propriétés des cycles.)
Voici rapidement quelques remarques utiles sur le contenu de ce document :
– La structure de liste n’étant pas autorisée, on utilisera des objets de type array.
– Les programmes (procédures et fonctions) seront toujours écrits avec la syntaxe proc(...)...end.
– On distinguera bien les procédures des fonctions.
Les deux structures reçoivent des arguments nécessaires à leur fonctionnement, mais :
(cid:5) Une fonction renvoie un résultat, directement utilisable dans une expression.
Par exemple, on écrira P:=identp(10) pour mettre l’identité de S10 dans la variable P .
Une fonction ne modifie pas les données qui lui sont extérieures (i.e. les variables globales.)
(cid:5) Une procédure ne renvoie aucun résultat, mais peut modifier le contenu des variables globales.
Si on écrit par exemple identp comme une procédure (recevant en argument un tableau et un
entier), l’instruction identp(P,10) aura pour effet de modifier le contenu de la variable P .
(cid:5) On utilisera toujours RETURN() pour forcer une procédure à ne renvoyer aucun résultat.
Algorithmique avec Maple
Permutations d’un ensemble fini
(cid:5) On utilisera toujours RETURN(...) pour préciser le résultat renvoyé par une fonction (bien
qu’avec Maple ce soit souvent inutile, le résultat étant celui de la dernière expression évaluée.)
– Pour gagner un peu en lisibilité, les identificateurs des procédures commenceront par une majuscule
et ceux des fonctions par une minuscule. On ne “typera” pas les variables locales. On désignera
seulement les “integer” par une lettre minuscule et les “array” par une lettre majuscule.
– Quand une procédure ou fonction utilise une procédure ou fonction précédemment écrite, l’identi-
ficateur de cette derniere est signalé en caracteres italiques dans le texte.
c(cid:13)EduKlub S.A.
Page 2
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Table des matières
Énoncé du problème
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Opérations sur les permutations . . . . . . . . . . . . . . . . . . . . . . . . . .
I.
Décomposition en cycles disjoints . . . . . . . . . . . . . . . . . . . . . . . . .
II.
Génération lexicographique de permutations . . . . . . . . . . . . . . . . . . .
III.
Génération récursive de permutations . . . . . . . . . . . . . . . . . . . . . . .
IV.
V.
. . . . . . . . . . . . . . . . .
Permutations ayant un nombre donné de cycles
Corrigé avec Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Opérations sur les permutations . . . . . . . . . . . . . . . . . . . . . . . . . .
I.
Décomposition en cycles disjoints . . . . . . . . . . . . . . . . . . . . . . . . .
II.
Génération lexicographique de permutations . . . . . . . . . . . . . . . . . . .
III.
Génération récursive de permutations . . . . . . . . . . . . . . . . . . . . . . .
IV.
V.
. . . . . . . . . . . . . . . . .
Permutations ayant un nombre donné de cycles
Indications pour les algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Rappels de cours
Notice bibliographique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
4
5
6
8
8
10
10
13
17
23
25
31
35
37
c(cid:13)EduKlub S.A.
Page 3
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Énoncé
Énoncé du problème
Voir en fin de document, pour des rappels de cours
Pour tout entier n ≥ 1, on note Sn le groupe des permutations de En = {1, 2, . . . , n}.
Un élément p de Sn sera représenté par P = [p(1), p(2), · · · , p(n)], tableau indicé de 1 à n.
Par exemple P = [5, 3, 1, 4, 6, 2] est l’élément p de S6 défini par
(cid:26) p(1) = 5, p(2) = 3, p(3) = 1
p(4) = 4, p(5) = 6, p(6) = 2
Dans toute la suite, on sera amené a programmer puis a utiliser des fonctions et des procédures
agissant sur des permutations p (i.e. sur les tableaux P associés.) On supposera que tout tableau
transmis en argument est valide. Plus généralement, on ne cherchera pas à vérifier que les arguments
reçus par une fonction ou une procédure sont conformes à ce qui est attendu.
On pourra cependant procéder à un typage minimal des arguments, en se limitant aux types integer
(entier relatif) et array(integer) (tableau d’entiers).
Bien sûr, quand une fonction est censée renvoyer une permutation (i.e. le tableau associé), il nous
appartiendra de faire en sorte que ce tableau soit valide !
Rappels
– L’expression array(1..n) renvoie un tableau indicé de 1 à n.
– L’expression rand( ) renvoie un entier pseudo-aléatoire à douze chiffres.
– Pour tout réel x, l’expression floor(x) renvoie l’entier “partie entière” de x.
– Pour tous entiers a et b > 0, a mod b ou irem(a, b) renvoient le reste dans la division de a par b.
Les expressions iquo(a, b) ou floor(a/b) donnent le quotient entier de cette division.
I. Opérations sur les permutations
1. Écrire une fonction identp créant la permutation identité dans Sn.
L’argument est un entier n ≥ 1, et le résultat est le tableau [1, 2, . . . , n].
[ S ]
2. Écrire une fonction randp créant une permutation p pseudo-aléatoire de Sn.
L’argument est un entier n ≥ 1, et le résultat est un tableau P = [p(1), p(2), . . . , p(n)].
[ S ]
3. Écrire une fonction comp composant deux permutations de Sn.
La syntaxe d’appel est comp(q, p, n) où n est dans N∗ et q, p dans Sn.
Le résultat renvoyé est la permutation q ◦ p (i.e. le tableau associé.)
Dans comp, on ne vérifiera pas que p et q désignent effectivement des éléments de Sn.
4. On se propose d’écrire une fonction powp calculant q = pm, où p est dans Sn et m dans N.
[ S ]
Avec la syntaxe d’appel powp(p, n, m), le résultat est le tableau associé à q = pm.
On donnera deux solutions, utilisant toutes deux un algorithme d’exponentiation rapide.
(a) La première solution sera itérative (non récursive).
[ S ]
c(cid:13)EduKlub S.A.
Page 4
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Énoncé
(b) La deuxième solution sera récursive.
[ S ]
5. Écrire une fonction invp calculant l’inverse d’une permutation p de Sn.
Avec la syntaxe invp(p, n), le résultat est le tableau Q associé à q = p−1.
On commencera par créer un tableau Q de longueur n, dont on affectera les différentes compo-
santes pour en faire le tableau associé à p−1.
[ S ]
II. Décomposition en cycles disjoints
1. Écrire une procédure inversant une permutation p de Sn “sur place”, donc sans utiliser (comme
dans I-5) un tableau auxiliaire de la taille de celui associé à p.
La syntaxe sera Invp(P, n). Invp ne renvoie aucun résultat (ce n’est pas une fonction).
Elle transforme le tableau P passé en argument en celui associé à la permutation inverse.
[Indication] [ S ]
2. Écrire une procédure transformant une permutation en sa décomposition en produits de cycles,
de la manière qui est décrite dans l’exemple suivant :
Considérons p =
(cid:18) 1 2 3 4 5 6 7 8
7 2 5 8 1 4 3 6
(cid:19)
= ( 1 7 3 5 ) ◦ ( 4 8 6 ).
Dans cet exemple decomp(p, 8) transformera p en [1, 7, 3, −5, −2, 4, 8, −6].
On devra donc former un tableau de même longueur que le tableau initial, faisant apparaˆıtre
les cycles successifs. La fin d’un cycle est marquée par un changement de signe.
Un point fixe étant un cycle de longueur 1, il est lui même affecté d’un changement de signe.
Avec ces conventions, [1, 7, 3, −5, −2, 4, 8, −6], [4, 8, −6, 1, 7, 3, −5, −2], [7, 3, 5, −1, −2, 6, 4, −8],
etc. sont des représentations valides de la décomposition d’une même permutation p.
On dira qu’une permutation p de Sn est “sous forme C” si le tableau qui la représente (et qui
est lui-même indicé de 1 à n) est construit avec les conventions indiquées précédemment.
Il n’y a évidemment pas unicité de la forme C d’une permutation p.
On dira que [p(1), p(2), . . . , p(n)] est la forme T de la permutation p.
La procédure Decomp transforme donc la forme T de p en l’une de ses formes C.
[ S ]
3. Écrire une procédure Recomp effectuant le travail inverse de Decomp.
La procédure Recomp transforme donc une forme C d’une permutation en sa forme T .
[ S ]
4. Dans cette question, on va calculer de deux manières différentes la signature d’une permutation.
(a) Écrire une fonction signat calculant la signature d’une permutation p de Sn.
La syntaxe sera signat(P, n) et le résultat sera ε(p).
On suppose ici que le tableau P est la forme usuelle (forme T ) de p.
On utilisera une méthode na¨ıve consistant à compter toutes les inversions de p.
[ S ]
(b) Réécrire la fonction signat en supposant que le tableau P transmis en argument est une
représentation sous forme C (comme fournie par Decomp) de la procédure p.
[ S ]
c(cid:13)EduKlub S.A.
Page 5
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Énoncé
5. Écrire une fonction ordre calculant l’ordre d’une permutation p (représentée par le tableau P
de sa décomposition en cycles, a la maniere de celui obtenu par la procédure Decomp.) [ S ]
6. En utilisant la décomposition en cycles fournie par la procédure Decomp, écrire une procédure
Powp calculant une puissance m quelconque (y compris négative) d’une permutation p de Sn.
La syntaxe d’appel sera Powp(P,n,m), où P est le tableau représentant p sous sa forme “tradi-
tionnelle” (c’est-à-dire sous la forme T ).
La procédure Powp ne renverra aucun résultat mais modifiera le tableau P pour en faire celui
associé à la permutation pm (toujours sous la forme T .)
Publicité
[Indication] [ S ]
III. Génération lexicographique de permutations
On se propose d’étudier une méthode “lexicographique” pour lister les éléments de Sn.
Une permutation p est ici représentée par le tableau P = [p(1), p(2), . . . , p(n)].
L’ensemble Sn est totalement ordonné par l’ordre lexicographique.
Pour cet ordre, le minimum de Sn est [1, 2, . . . , n-1, n] et le maximum est [n, n-1, . . . , 2, 1].
1. Écrire une procédure Nextp transformant un tableau P (donc une permutation p de Sn) en le
tableau qui représente la permutation suivante q.
La syntaxe est Nextp(P, n) et aucun résultat n’est renvoyé.
Si p est la permutation maximum de Sn, le tableau P n’est pas modifié.
[Indication] [ S ]
2. Écrire une fonction listp donnant les k permutations qui viennent à partir d’une permutation
p dans l’ordre lexicographique de Sn. La syntaxe d’appel sera Listp(P,n,k) et le résultat sera
un tableau de k lignes sur n colonnes (chaque ligne représentant une permutation, la première
ligne correspondant à la permutation de départ p.)
En déduire une fonction listallp renvoyant le tableau de toutes les permutations de Sn.
[ S ]
3. La méthode précédente permet d’ordonner complètement les éléments de Sn.
Chaque permutation reçoit donc un numéro d’ordre unique, de m = 0 pour P = [1, 2, . . . , n]
(la permutation identité), à m = n! − 1 pour P = [n, . . . , 2, 1].
Il est intéressant de pouvoir extraire une permutation à partir d’un numéro d’ordre, ou au
contraire de connaˆıtre le numéro d’ordre d’une permutation donnée.
Cela est possible grâce à une méthode appelée codage de Lehmer.
Définition (Code de Lehmer d’une permutation)
Soit p une permutation de Sn, avec n ≥ 2.
Le code de Lehmer de p est n-uplet L(p) = (c1, c2, . . . , cn−1, cn) défini par :
Pour tout i de {1, . . . , n}, ci est le nombre d’indices j de {i+1, . . . , n} tels que p(j) < p(i).
Chaque ci est donc le nombre d’inversions (i, j) de p, avec i < j. Ainsi 0 ≤ ci ≤ n-i.
Par construction L(p) est dans Fn = {0, . . . , n-1} × {0, . . . , n-2} × · · · × {0, 1} × {0}.
c(cid:13)EduKlub S.A.
Page 6
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Énoncé
Question : écrire une fonction code donnant le code de Lehmer d’une permutation p.
La syntaxe d’appel sera code(P,n) et le résultat sera le tableau [c1, c2, . . . , cn].
[ S ]
4. Avec les notations précédentes, on remarque que pour tout i de {1, . . . , n}, on a ci < p(i).
C’est en effet une conséquence des conditions p(j) < p(i) dans la définition.
Question : écrire une procédure Code transformant le tableau P représentant une permutation
de Sn en le tableau représentant son code de Lehmer (la syntaxe est Code(P, n).)
Pour cela, on imaginera une méthode de “descente” de [p(1), . . . , p(n)] vers [c1, . . . , cn].
[Indication] [ S ]
5. En cherchant à inverser la méthode précédente, écrire une procédure Decode permettant de
reformer le tableau associé a une permutation p, a partir de son code de Lehmer P = L(p). La
syntaxe est Decode(P, n).
Comme d’habitude, on ne vérifiera pas que le tableau P = [c1, c2, . . . , cn] donné en argument
est “valide”, c’est-à-dire que chaque ck est un entier de {0, . . . , n−k}.
[ S ]
6. Soit p une permutation de Sn, représentée par le tableau P = [p(1), p(2), . . . , p(n)].
Soit L(p) = [c1, c2, . . . , cn−1, cn = 0] le code de Lehmer de p.
On lui associe le “rang” de p, défini par :
rg(p) = c1(n−1)! + c2(n−2)! + · · · + cn−11! + cn0! =
On verra l’interprétation de cette fonction dans la question suivante.
On sait que chaque entier ck vérifie 0 ≤ ck ≤ n−k.
n
P
k=1
On remarque aussi que
(n−k)(n−k)! =
n
P
k=1
((n+1−k)!−(n−k)!) = n!−1.
n
P
k=1
ck(n−k)!
On définit ainsi une application p 7→ rg(p) de Sn dans {0, 1, . . . , n!−1}.
Question : écrire une fonction calculant le rang d’une permutation p.
La syntaxe sera rang(P, n), où P = [p(1), p(2), . . . , p(n)].
NB : pour calculer rg(p), on n’utilisera pas la fonction factorielle. . . [ S ]
7. On rappelle la notation Fn = {0, . . . , n−1} × {0, . . . , n−2} × · · · × {0, 1} × {0}.
L’ensemble Fn, qui est de cardinal n!, est totalement ordonné par l’ordre lexicographique.
– Montrer que le code de Lehmer définit une application strictement croissante de Sn sur Fn.
– Montrer que l’application p 7→ rg(p) est strictement croissante de Sn sur {0, . . . , n!−1}.
Elle permet donc de “numéroter” les éléments de Sn dans l’ordre lexicographique.
– En inversant cette application, on retrouve une permutation à partir de son numéro d’ordre.
Écrire une fonction gnar (l’inverse de la fonction rang) qui donne p dans Sn à partir de son
rang r. La syntaxe sera gnar(n, r) et le résultat sera le tableau [p(1), p(2), . . . , p(n)].
Le point essentiel est bien sûr l’algorithme qui permet de retrouver le tableau [c1, c2, . . . , cn]
(le code de Lehmer), à partir de r =
ck(n−k)!
n
P
k=1
– En déduire une nouvelle fonction randp de calcul d’une permutation pseudo-aléatoire de Sn.
[ S ]
c(cid:13)EduKlub S.A.
Page 7
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Énoncé
IV. Génération récursive de permutations
Dans cette partie, on voit deux méthodes pour former toutes les permutations p de l’ensemble Sn.
Les deux méthodes décrites ici utilisent une approche récursive.
1. Écrire une procédure Printp qui affiche successivement tous les éléments de Sn.
On respectera la contrainte suivante (que l’on considèrera comme une indication de l’algorithme
à utiliser) : si p et q sont deux éléments de Sn, la permutation p sera affichée avant la permutation
q si p−1 est située avant q−1 dans l’ordre lexicographique.
[Indication] [ S ]
2. Dans cette question, on engendre récursivement Sn par une méthode d’échanges successifs.
(a) On suppose que l’entier n est supérieur ou égal à 2.
Pour tout k de En = {1, . . . , n}, on note τk la transposition (k, n) (avec τ = id si k = n.)
[ S ]
Montrer que l’application ϕ : (σ, k) 7→ σ ◦ τk est une bijection de Sn−1 × En sur Sn.
(b) En déduire une nouvelle procédure Printp affichant tous les éléments de Sn.
On fera en sorte qu’apparaissent d’abord les permutations p telles que p(n) = n, puis
celles telles que p(n) = n − 1, etc., jusqu’à celles telles que p(n) = 1.
[ S ]
V. Permutations ayant un nombre donné de cycles
On sait que tout élément p de Sn peut être décomposé en un produit de cycles à supports disjoints
(et d’une maniere unique, a l’ordre près des facteurs.) Dans cette partie, on considérera qu’un point
fixe d’une permutation en est un cycle de longueur 1. Les supports des différents cycles intervenant
dans une permutation p forment donc une partition de l’ensemble En = {1, 2, . . . , n}.
Ainsi
p =
(cid:18) 1
2 3 4
9
5
10 5 9 4 14 3 1 15 12
6 7
8
10 11 12 13 14 15
11
7
13
8
6
2
(cid:19)
se décompose en
p = ( 1 10 7 ) ◦ ( 2 5 14 8 15 11 13 ) ◦ ( 3 9 12 6 ) ◦ ( 4 ).
On dira que cette permutation possède quatre cycles, de longueurs 1, 3, 4 et 7.
Tout élément p de Sn a donc k cycles, avec 1 ≤ k ≤ n. La somme des longueurs de ces cycles vaut n.
Pour 1 ≤ k ≤ n, on note (cid:2) n
k
Les coefficients (cid:2) n
k
(cid:3) le nombre de permutations dans Sn qui ont exactement k cycles.
(cid:3) sont appelés nombres de Stirling de premiere espece.
1. Dans cette question, on établit la relation qui permet de calculer les (cid:2) n
k
(cid:3), de (cid:2) n
(a) Préciser les valeurs de (cid:2) n
n−1
n
(cid:3)+(n−1)(cid:2) n−1
(cid:3) =(cid:2) n−1
(b) Prouver que (cid:2) n
k
k−1
k
(cid:3) et de (cid:2) n
1
(cid:3) (si 1 < k < n.) En déduire une sorte de triangle de
[ S ]
(cid:3), avec par exemple 1 ≤ k ≤ n ≤ 7.
Stirling permettant de calculer les coefficients (cid:2) n
k
(cid:3) de proche en proche.
[ S ]
(cid:3).
c(cid:13)EduKlub S.A.
Page 8
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
2. Déduire de la question précédente une fonction stir permettant de calculer les (cid:2) n
Avec la syntaxe stir(n) le résultat sera le tableau
h(cid:2) n
1
(cid:3), (cid:2) n
2
(cid:3), . . . , (cid:2) n
n
(cid:3)i
.
Énoncé
(cid:3).
k
NB : on utilisera un algorithme itératif, et un seul tableau (unidimensionnel de taille n.) [ S ]
3. Écrire une fonction randc renvoyant une permutation aléatoire p de Sn ayant k cycles.
Les différentes permutations solutions doivent pouvoir apparaˆıtre de façon équiprobable.
La syntaxe d’appel sera randc(n, k) et le résultat sera le tableau [p(1), p(2), . . . , p(n)].
On utilisera un procédé récursif, basé sur la formule de récurrence vue en V-1-b.
[Indication] [ S ]
4. Pour tout entier n ≥ 1, on définit l’application fn : x 7→ fn(x) =
(a) Montrer que fn(x) = x(x+1) · · · (x+n−1).
[ S ]
n
P
k=1
(cid:2) n
k
(cid:3)xk.
(b) On choisit aléatoirement (avec équiprobabilité) une permutation p de Sn.
On note Xn la variable aléatoire représentant le nombre de cycles de p.
Calculer l’espérance de Xn, et un équivalent de cette espérance quand n → ∞.
[ S ]
5. On va établir un résultat apparemment éloigné de ce qui précède...
On considère tout d’abord un tableau aléatoire Q = [a1, a2, . . . , an] de n éléments distincts d’un
ensemble totalement ordonné, par une relation notée <.
Publicité
(a) Écrire une fonction renvoyant le maximum des éléments du tableau Q.
[ S ]
(b) On dit qu’une valeur ak de Q est un record si k = 1 ou si : ∀j ∈ {1, . . . , k−1}, aj < ak.
Calculer l’espérance mathématique du nombre de records de Q...
[ S ]
c(cid:13)EduKlub S.A.
Page 9
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Corrigé
Corrigé avec Maple
I. Opérations sur les permutations
1. On forme un vecteur P de taille n, et on affecte gentiment chacune de ses composantes.
local P,k;
P:=array(1..n);
for k to n do P[k]:=k od; # ou encore : for k from 1 to n...
RETURN(eval(P))
ou encore : P:=vector(n)
renvoie le tableau P
> identp:=proc(n::integer)
>
>
>
>
> end:
Voici la permutation identité dans S7 :
> identp(7);
[ Q ]
[1, 2, 3, 4, 5, 6, 7]
2. On part de la permutation identité p représentée par le tableau P = [1, 2, . . . , n].
local P,j,k,t: P:=identp (n);
for k from n to 2 by -1 do
On échange P [n] = n avec P [j] = j, où j est choisi aléatoirement dans {1, . . . , n−1}.
On échange ensuite P [n−1] avec P [j], où j est aléatoire dans {1, . . . , n−2}.
De proche en proche, on construit ainsi une permutation p aléatoire.
> randp:=proc(n::integer)
>
>
>
>
>
>
> end:
On forme ici une permutation aléatoire de S10 :
> randp(10);
j:=1+(rand()mod n);
t:=P[k]; P[k]:=P[j]; P[j]:=t;
P = permutation identité
pour k = n, n−1, . . . , 2
j ∈ [1, 2, . . . , k], aléatoire
échange P [k] et P [j]
od;
RETURN(eval(P));
renvoie la permutation aléatoire
[1, 7, 10, 8, 5, 2, 3, 6, 4, 9]
local P,j,k,t:
P:=identp (n);
for k to n-1 do
Avec plus de liberté sur “rand” on peut remplacer “rand()mod k” par “rand(k)()”.
On sait même que “rand(j..k)()” renvoie un entier aléatoire de [j, . . . , k].
Avec cette syntaxe élargie, on peut légèrement simplifier la fonction “randp”.
> randp:=proc(n::integer)
>
>
>
>
>
>
>
> end:
[ Q ]
j:=rand(k..n);
t:=P[k]; P[k]:=P[j]; P[j]:=t;
P = permutation identité
pour k = 1, 2, . . . , n−1
j ∈ [k, . . . , n], aléatoire
échange P [k] et P [j]
od;
RETURN(eval(P));
renvoie la permutation aléatoire
c(cid:13)EduKlub S.A.
Page 10
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Corrigé
3. Le résultat t = q ◦ p est représenté par un tableau T de taille n.
Pour chaque k de {1, . . . , n} on a t(k) = q(p(k)) c’est-à-dire T [k] = Q[P [k]].
> comp:=proc(Q::array(integer),P::array(integer),n::integer)
>
>
>
>
> end:
local T,k;
T:=array(1..n);
for k to n do T[k]:=Q[P[k]] od; # calcule t = q ◦ p
RETURN(eval(T));
crée un tableau indicé de 1 à n
renvoie la permutation composée
Voici un exemple d’utilisation.
> P:=array([5,2,6,7,3,4,1]); Q:=array([1,6,5,4,3,2,7]); T:=comp(Q,P,7);
P := [5, 2, 6, 7, 3, 4, 1]
Q := [1, 6, 5, 4, 3, 2, 7]
T := [3, 6, 2, 7, 5, 4, 1]
[ Q ]
4. L’algorithme d’exponentiation rapide est basé sur l’écriture binaire de l’exposant m.
Posons en effet m = bk . . . b1b0 =
Notons S l’ensemble des j de {0, . . . , k} tels que bj = 1. Alors m = P
bj2j (pour tout j, bj = 0 ou bj = 1.)
2j puis pm = Q
p2j .
k
P
j=0
Il suffit donc de calculer les tj = p2j . Or t0 = p et pour tout j on a tj+1 = t2
j .
On calcule les chiffres binaires bj de m par divisions successives par 2 (le premier dividende est
m, le suivant est le quotient entier de m par 2, etc.) Le chiffre bj est le reste dans la (j + 1)-ième
division : j est dans S si le dividende de la (j + 1)-ième division est impair.
j∈S
j∈S
(a) Solution itérative :
on initialise : q = Id
on recopie m dans k et p dans t
tant que l’exposant résiduel k est > 0
if k mod 2 = 1 then
Q:=comp (Q,T,n)
local Q,T,k;
Q:=identp (n);
k:=m; T:=copy(P);
while k>0 do
> powp:=proc(P::array(integer),n::integer,m::integer)
>
>
>
>
>
>
>
>
>
>
>
> end:
fi;
T:=comp (T,T,n);
k:=floor(k/2);
od;
RETURN(eval(Q));
renvoie la puissance m-ième de p
on élève t au carré
ou k:=iquo(k,2) : on divise k par 2
ou if type(k,odd), ou if irem(k,2)=1
si k est impair, on compose q et t
Sur cet exemple, on calcule la puissance quatrième d’une permutation de S9 :
> P:=array([8,6,1,3,4,5,2,9,7]); Q:=powp(P,9,4);
c(cid:13)EduKlub S.A.
Page 11
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Corrigé
P := [8, 6, 1, 3, 4, 5, 2, 9, 7]
Q := [2, 3, 7, 9, 8, 1, 4, 6, 5]
[ Q ]
(b) Solution récursive :
On note que si m ≥ 1, alors pm =
( (cid:0)pm/2(cid:1)2
p ◦ (cid:0)p(m−1)/2(cid:1)2
si m est pair
si m est impair
2 ), puis t2.
local Q;
if m=0 then RETURN(identp (n)) # si m = 0 alors c’est l’identité.
else
Pour calculer q = pm, on calcule donc t = pk, avec k = E( m
On multiplie ensuite le résultat par p si l’exposant m est impair.
Évidemment, si m = 0, alors pm = Id (c’est la condition d’arrêt de la plongée récursive.)
Pour la distinguer de la précédente, on a nommé powpr cette version récursive.
> powpr:=proc(P::array(integer),n::integer,m::integer)
>
>
>
>
>
>
>
>
>
fi
>
> end:
[ Q ]
Q:=powpr (P,n,iquo(m,2));
Q:=comp (Q,Q,n);
if type(m,odd) then
Q:=comp (P,Q,n)
appel récursif, avec exposant moitié
élève le résultat au carré
si m impair,
fi;
RETURN(eval(Q));
renvoie la puissance m-ième de p
on compose par p
Publicité
si m ≥ 1,
5. La permutation p est représentée par le tableau P = [p(1), p(2), . . . , p(n)].
Soit Q = [q(1), q(2), . . . , q(n)] le tableau associé à q = p−1.
Alors, pour tout entier k de {1, 2, . . . , n} on a q(p(k)) = k donc Q[P [k]] = k.
Une simple boucle permet donc de placer les k successifs dans le tableau Q.
> invp:=proc(P::array(integer),n::integer)
>
>
>
>
> end:
Sur cet exemple, on calcule q = p−1 et on vérifie que q ◦ p = id.
> P:=array([4,6,2,9,3,8,1,7,5]); Q:=invp(P,9); comp(Q,P,9);
local Q,k;
Q:=array(1..n);
for k to n do Q[P[k]]:=k od; # boucle d’affectation des composantes de Q
RETURN(eval(Q));
renvoie la permutation inverse de p
le tableau Q qui va représenter l’inverse de p
P := [4, 6, 2, 9, 3, 8, 1, 7, 5]
Q := [7, 3, 5, 1, 9, 2, 8, 6, 4]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[ Q ]
c(cid:13)EduKlub S.A.
Page 12
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Corrigé
II. Décomposition en cycles disjoints
1. Voici la procédure Invp, fidèle traduction des indications de l’énoncé.
local i,j,k,t:
for i to n do
j:=i; k:=P[j];
while P[i]>0 do
t:=P[k];
P[k]:=-j;
j:=k;
k:=t
boucle de parcours du tableau
deux indices: k = p(j). Au départ j = i.
tant que le cycle partant de i n’est pas traité
> Invp:=proc(P::array(integer),n::integer)
>
>
>
>
>
>
>
>
>
>
>
>
> end:
Voici un exemple d’utilisation (avec la permutation p évoquée dans l’énoncé.)
On notera que le tableau représentant p est modifié par la procédure Invp.
> P:=array([7,2,5,8,1,4,3,6]): Invp(P,8); eval(P);
sauvegarde l’image de k.
écrit et ‘‘taggue’’ l’image réciproque p −1 (k) = j
passe à l’élément qui suit j dans le cycle
récupère l’image k = p(j)
restaure le signe d’un l’élément ‘‘taggué’’
od;
P[i]:=-P[i];
aucun résultat renvoyé
od;
RETURN();
[ Q ]
2. Voici la procédure Decomp.
[5, 2, 7, 6, 3, 8, 1, 4]
while Q[j]>0 do
une copie de la permutation à décomposer
initialise le pointeur dans le tableau P
boucle de parcours du tableau Q
local Q,i,j,k;
Q:=copy(P);
i:=0;
for j to n do
i:=i+1: P[i]:=j;
j:=Q[j];
Q[P[i]]:=0;
if Q[j]=0
> Decomp:=proc(P::array(integer),n::integer)
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> end:
Voici un exemple d’utilisation, avec la permutation citée dans l’énoncé.
P:=array([7,2,5,8,1,4,3,6]): Decomp(P,8); eval(P);
tant que le cycle en cours n’est pas terminé,
écrit l’élément courant dans le tableau P
passe à l’élément suivant dans le cycle
marque comme lu le dernier élément traité dans Q
si le cycle est terminé,
marque la fin par un changement de signe
ne renvoie aucun résultat
od;
RETURN()
then P[i]:=-P[i]
od;
fi;
[1, 7, 3, −5, −2, 4, 8, −6]
c(cid:13)EduKlub S.A.
Page 13
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Corrigé
Remarque : on constate que l’indice j de la boucle for subit des modifications dans le corps de
cette boucle, à l’intérieur de la structure while...do...od. En fait, l’indice j décrit un cycle
de la permutation, et il reprend à la sortie du while la valeur qu’il avait en y entrant.
[ Q ]
3. Voici la procédure Recomp.
Le tableau initial P est recopié dans une variable Q.
Le tableau Q est ensuite parcouru sur toute sa longueur.
Au fur et à mesure de ce parcours, la recomposition s’effectue dans le tableau P .
On notera l’utilisation de la fonction abs pour les affectations dans P , de façon à neutraliser
les changements de signe qui correspondent à des fins de cycle. On notera enfin l’utilisation de
la variable locale d, dont le rôle est de mémoriser le début du cycle en cours de traitement.
local Q,j,d;
Q:=copy(P);
for j to n do
d:=Q[j];
while Q[j]>0 do
> Recomp:=proc(P::array(integer),n::integer)
>
>
>
>
>
>
>
>
>
>
>
> end:
P[Q[j]]:=abs(Q[j+1]);
j:=j+1;
od;
P[abs(Q[j])]:=abs(d);
od;
RETURN()
une copie de la permutation à décomposer
boucle de parcours du tableau Q
c’est le début d’un cycle
tant que le cycle n’est pas terminé,
complète la recomposition de la permutation
passe à l’élément suivant dans Q
termine le traitement du cycle
aucun résultat renvoyé
Sur cet exemple, on décompose puis on recompose une permutation p.
> P:=array([7,2,5,8,1,4,3,6]); Decomp(P,8); eval(P); Recomp(P,8); eval(P);
P := [7, 2, 5, 8, 1, 4, 3, 6]
[1, 7, 3, −5, −2, 4, 8, −6]
[7, 2, 5, 8, 1, 4, 3, 6]
On voit ici que Recomp rétablit la forme T d’une permutation à partir de l’une quelconque de
ses formes C (et donc pas seulement à partir de celle qui a été fournie par Decomp.)
> P:=array([-2,8,6,-4,3,5,1,-7]); Recomp(P,8), eval(P);
[ Q ]
P := [−2, 8, 6, −4, 3, 5, 1, −7]
[7, 2, 5, 8, 1, 4, 3, 6]
c(cid:13)EduKlub S.A.
Page 14
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Algorithmique avec Maple
Permutations d’un ensemble fini
Corrigé
4. On va nommer signat et signatc les deux versions successives de la fonction “signature”.
(a) Voici la fonction signat.
for j from i+1 to n do
local s,i,j;
s:=1;
for i to n-1 do
> signat:=proc(P::array(integer), n::integer)
>
>
>
>
>
>
>
>
> end:
[ Q ]
if P[j]<P[i] then s:=-s; fi;
od;
RETURN(s);
od