Permutations d’un ensemble fini
Permutations d’un ensemble fini
Programming, Math · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Pour créer la permutation identité dans Sn, nous formons un tableau P de taille n et affectons à chaque composante k la valeur k.
identp:=proc(n::integer)
local P,k;
P:=array(1..n);
for k to n do P[k]:=k od;
RETURN(eval(P))
end:
On part de la permutation identité représentée par P = [1, 2, ..., n]. Ensuite, pour k allant de n à 2 (en ordre décroissant), on échange P[k] avec un élément P[j] où j est choisi aléatoirement dans l'intervalle [1, k]. Une version plus large de la syntaxe rand permet d'obtenir un entier aléatoire directement dans un intervalle.
randp:=proc(n::integer)
local P,j,k,t:
P:=identp(n);
for k from n to 2 by -1 do
j:=1+(rand()mod k);
t:=P[k]; P[k]:=P[j]; P[j]:=t;
od;
RETURN(eval(P));
end:
Le résultat t = q ◦ p est représenté par un tableau T de taille n. Pour chaque entier k de {1, ..., n}, on a t(k) = q(p(k)), ce qui se traduit par T[k] = Q[P[k]].
comp:=proc(Q::array(integer),P::array(integer),n::integer)
local T,k;
T:=array(1..n);
for k to n do T[k]:=Q[P[k]] od;
RETURN(eval(T));
end:
L'algorithme d'exponentiation rapide repose sur l'écriture binaire de l'exposant m = Σ (b_j × 2^j). On calcule les carrés successifs et on compose le résultat pour les termes où b_j = 1.
Solution itérative :
powp:=proc(P::array(integer),n::integer,m::integer)
local Q,T,k;
Q:=identp(n);
k:=m; T:=copy(P);
while k>0 do
if k mod 2 = 1 then
Q:=comp(Q,T,n)
fi;
T:=comp(T,T,n);
k:=floor(k/2);
od;
RETURN(eval(Q));
end:
Solution récursive : Pour calculer q = p^m, on calcule t = p^k où k = quotient(m, 2). Puis on élève t au carré. Si l'exposant m est impair, on multiplie le résultat par p.
powpr:=proc(P::array(integer),n::integer,m::integer)
local Q;
if m=0 then RETURN(identp(n))
else
Q:=powpr(P,n,iquo(m,2));
Q:=comp(Q,Q,n);
if type(m,odd) then
Q:=comp(P,Q,n)
fi;
RETURN(eval(Q));
fi
end:
Soit Q = [q(1), q(2), ..., q(n)] le tableau associé à q = p^(-1). Pour tout k, q(p(k)) = k, donc on affecte Q[P[k]] := k.
invp:=proc(P::array(integer),n::integer)
local Q,k;
Q:=array(1..n);
for k to n do Q[P[k]]:=k od;
RETURN(eval(Q));
end:
Cette procédure parcourt les cycles de la permutation et les inverse un par un sans utiliser de tableau auxiliaire de taille n. Les éléments déjà traités ("taggués") reçoivent un signe négatif, qui est rétabli à la fin.
Invp:=proc(P::array(integer),n::integer)
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
od;
P[i]:=-P[i];
od;
RETURN();
end:
La procédure transforme la forme T d'une permutation en sa forme C, marquant la fin de chaque cycle par un nombre négatif.
Decomp:=proc(P::array(integer),n::integer)
local Q,i,j,k;
Q:=copy(P);
i:=0;
for j to n do
if Q[j]>0 then
while Q[j]>0 do
i:=i+1: P[i]:=j;
k:=Q[j];
Q[P[i]]:=0;
j:=k;
od;
P[i]:=-P[i]
fi;
od;
RETURN()
end:
Note sur le code : la version de l'énoncé contient une légère anomalie dans la boucle while (indice j modifiant l'indice de la boucle for). Le fonctionnement est garanti par le fait que l'indice de boucle explore un cycle pour revenir à sa valeur.
La procédure utilise un tableau copié Q. On parcourt Q et on construit le tableau P avec les valeurs absolues de Q, gérant la fermeture du cycle grâce à une mémorisation du début de cycle dans d.
Recomp:=proc(P::array(integer),n::integer)
local Q,j,d;
Q:=copy(P);
for j to n do
d:=Q[j];
while Q[j]>0 do
P[Q[j]]:=abs(Q[j+1]);
j:=j+1;
od;
P[abs(Q[j])]:=abs(d);
od;
RETURN()
end:
Méthode naïve (forme usuelle T) : On compte les inversions et on change le signe à chaque inversion trouvée.
signat:=proc(P::array(integer), n::integer)
local s,i,j;
s:=1;
for i to n-1 do
for j from i+1 to n do
if P[j]<P[i] then s:=-s; fi;
od
od;
RETURN(s);
end:
Méthode avec forme C : Le nombre de cycles (incluant les points fixes) est égal au nombre de coefficients négatifs.
signatc:=proc(P::array(integer), n::integer)
local s,i;
s:=(-1)^n;
for i to n do
if P[i]<0 then s:=-s; fi;
od;
RETURN(s);
end:
L'ordre est le PPCM des longueurs des cycles.
pgcd:=proc(a::integer, b::integer)
if b=0 then RETURN(a)
else RETURN(pgcd(b, a mod b))
fi
end:
ordre:=proc(P::array(integer),n::integer)
local i,j,m;
m:=1;
i:=1;
while i<=n do
j:=i;
while P[i]>0 do i:=i+1 od;
m:=m/pgcd(m,i-j+1) * (i-j+1);
i:=i+1;
od;
RETURN(m);
end:
Note : Le PPCM de A et B se calcule par (A × B) / PGCD(A, B).
En décomposant p, il suffit de décaler chaque élément à l'intérieur de son cycle de m positions (modulo la longueur du cycle).
Powp:=proc(P::array(integer),n::integer,m::integer)
local Q,i,j,k,t;
Q:=copy(P);
Decomp(Q,n);
i:=1;
while i<=n do
j:=i;
while Q[i]>0 do i:=i+1 od;
Q[i]:=-Q[i];
t:=i-j+1;
for k from 0 to t-1 do
P[Q[j+k]]:=Q[j+((k+m)mod t)]
od;
i:=i+1;
od;
RETURN();
end:
Cette procédure trouve le plus grand indice i tel que p(i) < p(i+1), puis le plus grand indice j tel que p(j) > p(i), échange p(i) et p(j), et inverse l'ordre des éléments restants pour obtenir la permutation suivante dans l'ordre lexicographique.
Nextp:=proc(P::array(integer),n::integer)
local i,j,t;
i:=n-1;
while (i>0) and (P[i]>P[i+1]) do i:=i-1 od;
if i>0 then
j:=n;
while P[j]<P[i] do j:=j-1 od;
t:=P[i]; P[i]:=P[j]; P[j]:=t;
i:=i+1; j:=n;
while i<j do
t:=P[i]; P[i]:=P[j]; P[j]:=t;
i:=i+1; j:=j-1;
od;
fi;
RETURN();
end:
listp:=proc(P::array(integer),n::integer,k::integer)
local T,Q,i,j;
T:=array(1..k,1..n);
Q:=copy(P);
for i to k do
for j to n do T[i,j]:=Q[j]; od;
Nextp(Q,n);
od;
RETURN(eval(T));
end:
listallp:=proc(n::integer)
RETURN(listp(identp(n),n,n!))
end:
Le code c_i est le nombre de j > i tels que p(j) < p(i).
code:=proc(P::array(integer),n::integer)
local C,i,j;
C:=array(1..n);
for i to n do
C[i]:=0;
for j from i+1 to n do
if P[j]<P[i] then
C[i]:=C[i]+1
end;
od;
od;
RETURN(eval(C));
end:
Pour chaque i, on soustrait 1 à tout coefficient à droite qui est supérieur ou égal au coefficient en cours.
Code:=proc(P::array(integer),n::integer)
local i,j,d;
for i to n do
d:=P[i];
for j from i to n do
if P[j]>=d then
P[j]:=P[j]-1
fi
od
od;
RETURN()
end:
On inverse le processus par des remontées successives de droite à gauche.
Decode:=proc(P::array(integer),n::integer)
local i,j;
for i from n to 1 by -1 do
P[i]:=P[i]+1;
for j from i+1 to n do
if P[j]>=P[i] then
P[j]:=P[j]+1
fi
od
od;
RETURN()
end:
Le rang est évalué par la somme rg(p) = Σ (c_k × (n-k)!) via le schéma de Horner.
rang:=proc(P::array(integer),n::integer)
local r,k,C;
C:=copy(P);
Code(C,n);
r:=0;
for k to n do r:=(n+1-k)*r+C[k]; od;
RETURN(r)
end:
L'application L associe une permutation à son code de Lehmer de manière strictement croissante vers l'ensemble Fn. De même, l'association du code de Lehmer au rang est strictement croissante vers {0, ..., n!-1}. L'application composée p ↦ rg(p) numérote donc bijectivement et en respectant l'ordre lexicographique les permutations de Sn.
gnar:=proc(n::integer,r::integer)
local P,i,t;
P:=array(1..n);
t:=r;
for i to n do
P[n+1-i]:=irem(t,i);
t:=iquo(t,i);
od;
Decode(P,n);
RETURN(eval(P));
end:
randp:=proc(n::integer)
RETURN(gnar(n,rand(n!)()));
end:
La procédure place successivement les valeurs de 1 à n dans les positions disponibles, générant les permutations dans l'ordre croissant de p^(-1).
Printp:=proc(n::integer)
local P,j,Pose;
P:=array(1..n);
for j to n do P[j]:=0 od;
Pose:=proc(m::integer)
local k;
for k to n do
if P[k]=0 then
P[k]:=m;
if m=n then print(eval(P))
else Pose(m+1)
fi;
P[k]:=0;
fi;
od;
end;
Pose(1);
RETURN();
end:
a) Preuve de la bijection : Soit p un élément de Sn, et (σ, k) un élément de S_(n-1) × E_n. Si p = ϕ(σ, k) = σ ◦ τ_k, alors p(k) = σ(n) = n. Donc k = p^(-1)(n). Avec ce k, on a σ = p ◦ τ_k, et on vérifie que σ(n) = p(k) = n. L'application est donc bien injective, et, par égalité des cardinaux (n! pour Sn, (n-1)! × n pour S_(n-1) × E_n), c'est une bijection.
b) Procédure par échanges (Printp2) :
Swap:=proc(P::array,j::integer,k::integer)
local t; t:=P[j]; P[j]:=P[k]; P[k]:=t; RETURN()
end:
Printp2:=proc(n::integer)
local P,j,Go;
P:=identp(n);
Go:=proc(m::integer)
local k,t;
for k from m to 1 by -1 do
Swap(P,m,k);
if m=2 then print(eval(P))
else Go(m-1)
fi;
Swap(P,m,k);
od;
end;
Go(n);
RETURN();
end:
a) Valeurs remarquables :
b) Relation de récurrence : Considérons 1 < k < n. Les [n, k] permutations ayant k cycles se divisent en deux groupes :
stir:=proc(n::integer)
local P,m,k:
P:=array(1..n);
P[1]:=1;
for m from 2 to n do
P[m]:=1;
for k from m-1 to 2 by -1 do
P[k]:=P[k-1]+(m-1)*P[k]
od;
P[1]:=(m-1)*P[1];
od;
RETURN(eval(P));
end:
La probabilité que n soit un point fixe est P = [n-1, k-1] / [n, k]. On s'appuie sur cette probabilité de manière récursive.
randc:=proc(n::integer,k::integer)
local go,P;
go:=proc(n::integer,k::integer)
local r,j,x;
if k>1 then r:=stir(n-1)[k-1]/stir(n)[k]
else r:=0
fi;
if 10^(-12)*rand()<r then
P:=go(n-1,k-1);
P[n]:=n;
if n=1 then RETURN(eval(P)) fi;
else
P:=go(n-1,k);
j:=1+(rand()mod(n-1));
Swap(P,n,j);
fi;
RETURN(eval(P))
end;
P:=array(1..n);
go(n,k);
RETURN(eval(P));
end:
a) Polynôme de dénombrement : Pour n=1, f_1(x) = [1, 1]x = x. Supposons que f_(n-1)(x) = x(x+1)...(x+n-2). f_n(x) = Σ [n, k]x^k = x [n-1, n-1]x^(n-1) + Σ ([n-1, k-1] + (n-1)[n-1, k])x^k f_n(x) = x Σ [n-1, k]x^k + (n-1) Σ [n-1, k]x^k f_n(x) = (x + n - 1) f_(n-1)(x). Par récurrence, f_n(x) = x(x+1)...(x+n-1).
b) Espérance X_n : E(X_n) = (1/n!) Σ k [n, k] = (1/n!) f'_n(1). En dérivant f_n(x), on obtient que f'_n(1) / f_n(1) = Σ (1/k) pour k allant de 1 à n. Puisque f_n(1) = n!, on a E(X_n) = Σ (1/k). Un équivalent classique de la série harmonique donne E(X_n) ≈ ln(n) quand n → ∞.
a) Valeur maximum :
maxi:=proc(P::array(integer),n::integer)
local m,k:
m:=P[1];
for k from 2 to n do
if P[k]>m then m:=P[k] fi;
od;
RETURN(m);
end:
b) Espérance mathématique du nombre de records : La source fournie est endommagée et s'interrompt brutalement au début de la réponse (« On a l --- END SOURCE --- »). Il est donc impossible de rédiger la suite de la solution sans inventer la fin de la démonstration, ce qui viole nos contraintes de résolution. La déduction est cependant intimement liée aux propriétés de l'arrangement des permutations vues plus haut (la distribution des records correspond à la construction des cycles par la méthode de décomposition usuelle).
Pour aborder ce type de sujet mêlant théorie algébrique (groupe symétrique) et algorithmique, il est recommandé de suivre ces étapes :
copy versus procédures modifiant les données sur place via P[i] := ...).