Page d'accueil
Thèmes d'activités
<< Thème précédent
Thème suivant >>
Énumérations d'ensembles finis
d'après l'épreuve d'informatique ESIM 99 MP
Corrigé du thème
La procédure
premier
(e::list) rend le premier élément d'une liste e.
La procédure
sauf_premier
(e::list) rend la liste obtenue en enlevant le premier élément de la liste e.
La procédure
sauf_ieme
(i::posint,e::list) rend la liste obtenue en enlevant le i-ème élément de la liste e.
La procédure
ieme
(i::posint,e::list) rend le i-ème élément de la liste e.
La procédure
ajout
(e,L::list(list)) rend la liste de listes obtenue en ajoutant l'élément e comme premier
élément à chacune des listes composant L.
Dans toute la suite, contrairement à l'usage, on représente un
ensemble
par la
liste
de ses éléments.
Exemple:
L'ensemble
sera donc représenté par la liste
.
La procédure
parties
(e::list) rend la liste de toutes les parties de l'ensemble e.
La procédure
combinaisons
(p::nonnegint,e::list) rend la liste des parties à p éléments de l'ensemble e.
La procédure
permutations
(e::list) rend la liste des permutations de l'ensemble e.
La procédure
bijections
(e::list,f::list) rend la liste des bijections de l'ensemble e vers l'ensemble f.
La procédure
surjections
(e::list,f::list) rend la liste des surjections de l'ensemble e sur l'ensemble f.
La procédure
nb_surjections
(n::nonnegint,p::nonnegint) rend le nombre de surjections d'un ensemble
à n éléments sur un ensemble à p éléments.
La procédure
partition
(e::list) rend la liste des partitions de l'ensemble e.
Corrigé:
Énoncé du thème
>
premier:=proc(e::list)
if nops(e)>0 then e[1] else error "l'ensemble doit être non vide" end if;
end proc;
>
premier([a,b,c,d]);
>
sauf_premier:=proc(e::list)
local j,L;
L:=NULL;
for j to nops(e) do
if j<>1 then L:=L,e[j] end if
end do;
[L];
end proc;
>
sauf_premier([a,b,c,d]);
>
sauf_ieme:=proc(i::posint,e::list)
local j,L;
L:=NULL;
for j to nops(e) do
if j<>i then L:=L,e[j] end if
end do;
[L];
end proc;
>
sauf_ieme(3,[a,b,c,d]);
>
ieme:=proc(i::posint,e::list)
if 1<=i and i<=nops(e) then e[i] else error "mauvais argument" end if;
end proc;
>
ieme(3,[a,b,c,d]);
>
ajout:=proc(e,L::list(list))
local i,M;
M:=NULL;
for i to nops(L) do
M:=M,[e,op(L[i])]
end do;
[M]
end proc;
>
ajout(a,[[b,c,d],[alpha,beta],[],[1,2,3,4]]);
>
parties:=proc(e::list)
local x,f,part;
if e=[] then [[]]
else
x:=premier(e);f:=sauf_premier(e);
part:=parties(f);
[op(part),op(ajout(x,part))]
end if;
end proc;
>
parties([]);
>
parties([a]);
>
parties([a,b]);
>
parties([a,b,c]);
>
parties([a,b,c,d]);
>
combinaisons:=proc(p::nonnegint,e::list)
local x,f;
if p>nops(e) then []
else
if p=0 then [[]]
else
x:=premier(e);f:=sauf_premier(e);
[op(ajout(x,combinaisons(p-1,f))),op(combinaisons(p,f))]
end if;
end if;
end proc;
>
combinaisons(1,[a,b]);
>
combinaisons(3,[a,b,c,d,e,f]);
>
permutations:=proc(e::list)
local L,i,n,x,ei;
n:=nops(e);
L:=NULL;
if n=1 then [[premier(e)]] else
for i to n do
x:=ieme(i,e);ei:=sauf_ieme(i,e);
L:=L,op(ajout(x,permutations(ei)));
end do;
[L]
end if;
end proc;
>
permutations([a,b,c]);
>
permutations([a,b,c,d]);
>
bijections:=proc(e::list,f::list)
local L,j,n,p,x,y,e1,fj;
n:=nops(e);p:=nops(f);
if n<>p or n=0 then []
else
x:=premier(e);e1:=sauf_premier(e);
if n=1 then [[cat(`(`,convert(x,string),`,`,convert(premier(f),string),`)`)]] else
L:=NULL;
for j to p do
y:=ieme(j,f);fj:=sauf_ieme(j,f);
L:=L,op(ajout(cat(`(`,convert(x,string),`,`,convert(y,string),`)`),bijections(e1,fj)));
end do;
[L]
end if;
end if;
end proc;
>
bijections([a],[1,2]);
>
bijections([a],[1]);
>
bijections([a,b,c],[1,2,3]);
>
surjections:=proc(e::list,f::list)
local L,j,n,p,x,y,e1,fj;
n:=nops(e);p:=nops(f);
if n<p or n=0 or p=0 then []
else
x:=premier(e);e1:=sauf_premier(e);
if n=1 then # car alors n=p=1
[[cat(`(`,convert(x,string),`,`,convert(premier(f),string),`)`)]]
else
L:=NULL;
for j to p do
y:=ieme(j,f);fj:=sauf_ieme(j,f);
L:=L,op(ajout(cat(`(`,convert(x,string),`,`,convert(y,string),`)`),surjections(e1,fj))),
op(ajout(cat(`(`,convert(x,string),`,`,convert(y,string),`)`),surjections(e1,f)));
end do;
[L]
end if;
end if;
end proc;
>
surjections([a],[1,2]);
>
surjections([1,2,3,4,5,6,7],[a,b,c]):nops(%);
>
nb_surjections:=proc(n::nonnegint,p::nonnegint)
if n<p or n=0 or p=0 then 0
elif n=1 then 1
# car alors n=p=1
else p*(nb_surjections(n-1,p-1)+nb_surjections(n-1,p))
end if;
end proc;
>
nb_surjections(4,2);
>
nb_surjections(7,3);
>
partition:=proc(e::list)
local f,j,k,n,L,M;n:=nops(e);
if n=1 then RETURN([[e]])
else
L:=NULL;
f:=partition(sauf_premier(e));
for j to nops(f) do
M:=ieme(j,f);
L:=L,[[premier(e)],op(M)];
for k to nops(M) do
if nops(M)=1 then
L:=L,ajout(premier(e),[ieme(k,M)])
else
L:=L,[op(sauf_ieme(k,M)),op(ajout(premier(e),[ieme(k,M)]))]
end if;
end do;
end do;
end if;
[L]
end proc;
>
partition([a]);
>
partition([a,b]);
>
partition([a,b,c]);
>
p:=partition([a,b,c,d]): for k to nops(p) do op(k,p) end do;
|