Énumérer les arrangements possibles
Bonsoir !
Je souhaite écrire un programme qui énumère tous les arrangements (ou permutations) possibles de x dans x. C'est à dire, xPx.
Par exemple, on veut énumérer tous les nombres qu'on peut former en utilisant tous les chiffres donnés. Avec les chiffres 4, 9 et 7, la réponse doit être : "on peut former 497, 479, 794, 749, 947 et 974".
Pour cela, j'ai cherché un algorithme. En refléchissant un peu, j'en ai trouvé un qui me paraît assez intéressant. Toutefois, je l'ai "inventé" tout seul et cela veut dire qu'il y en a probablement un qui soit plus rapide ou plus facile à implémenter ou les deux. Mon algorithme est récursif. Pour trouver tous les arrangements avec n éléménts on doit d'abord connaître toutes les possibilités avec n-1 seulement. Une exécution vaut mieux qu'un long discours :
On va chercher tous les arrangements possibles avec "abcd". Il y en a 24(=4!).
On prend une matrice carrée de côté 4. On remplit toutes les cases de la diagonale avec a :
a . . .
. a . .
. . a .
. . . a
ensuite on insère bcd dans toutes les cases qui ne font pas partie de la diagonale :
a b c d
b a c d
b c a d
b c d a
Maintenant, il faut refaire la méme chose avec toutes les possibilités de bcd, telles que cbd :
a c b d
c a b d
c b a d
c b d a
C'était la 2e matrice, il y en a 6 pour ce cas particulièrement car il y a 6 arrangements possibles avec 3 éléments (b, c et d dans cet exemple)
Le contenu de cette matrice doit être recopié à présent dans un tableau (unidimensionel). Chaque ligne de la matrice est recopiée dans une case du tableau. Le résultat final est un tableau contenant toutes les possibilités avec n éléments. La taille du tableau est, par conséquent, n!.
Remarquez que pour connaître toutes les possibilités de bcd, il faut avoir fait la méme chose avant. Il faut mettre b dans la diagonale et remplir le reste des matrices avec à chaque fois un arrangement de cd. C'est là que se montre le caractère récursif de l'algorithme.
Avant de me donner d'autres façons de trouver, je vous prie de m'aider à implémenter celle-là. J'ai tout codé mais je n'ai pas eu le temps de commenter, je m'en excuse.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| program a914;
uses wincrt;
type mat=array[1..10,1..10]of char;
table=array[1..100] of string;
var t:table; i,j,k:integer; N:string;
function factorielle(n:integer):integer;
begin
if n>1 then factorielle:=n*factorielle(n-1);
end;
procedure acm(var t:table; m:mat; n,x:integer);
var i,j:integer;
begin
for i:=1 to n do for j:=1 to n do t[i+x]:=t[i+x]+m[i,j];
end;
procedure arrangement(var t:table; N:string);
var m:mat; i,j,k,x,p:integer; ch:string; a:char;
begin
if length(N)>1 then
begin
a:=N[1]; delete(N,1,1);
arrangement(t,N);
for k:=1 to factorielle(length(N)) do
begin
ch:=t[k];
for i:=1 to length(N)+1 do
begin
p:=1;
for j:=1 to length(N)+1 do
begin
if i=j then m[i,j]:=a
else begin m[i,j]:=N[p]; p:=p+1 end;
end;
end;
x:=x+length(N)+1;
acm(t,m,length(N)+1,x);
end;
end;
end;
BEGIN
write('donnez un entier ');
readln(N);
writeln('Les possiblilités d''arrangements sont :');
arrangement(t,N); for i:=1 to factorielle(length(N)) do writeln(t[i]);
END. |
La procédure acm copie les lignes d'une matrice m dans une case du tableau t chacune, et à partir de la case x du tableau.
Je ne sais pas où se trouve l'erreur.
Merci énormément à tous ceux qui ont lu ne serait-ce qu'une partie de tout ça :)
Merci particulièrement à ceux qui ont tout lu.
