Discussion :

[katrena99]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[droggo]

Fio,

Je n'ai pas regardé le code, juste un coup d'oeil, et j'ai déjà bondi jusqu'au plafond:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
function factorielle(n:integer):integer;
begin
if n>1 then factorielle:=n*factorielle(n-1);
end;

La récursivité pour calculer une factorielle fait partie des cas où cette utilisation est totalement absurde.

Je sais, c'est un exemple assez typique dans les cours, mais ça ne fait que montrer que les cours sont mal faits.

En plus, ta fonction est fausse : que va-t'elle renvoyer si n = 0 ou 1 ?

[katrena99]

Bonsoir droggo !
Me revoilà, j'ai de sérieux problèmes de connexion, je n'ai plus internet chez moi. C'est pour ça que je mets autant de temps à répondre.

Fio,

Je n'ai pas regardé le code, juste un coup d'oeil, et j'ai déjà bondi jusqu'au plafond:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
function factorielle(n:integer):integer;
begin
if n>1 then factorielle:=n*factorielle(n-1);
end;

La récursivité pour calculer une factorielle fait partie des cas où cette utilisation est totalement absurde.

Je sais, c'est un exemple assez typique dans les cours, mais ça ne fait que montrer que les cours sont mal faits.

En plus, ta fonction est fausse : que va-t'elle renvoyer si n = 0 ou 1 ?

Non je n'ai pas trouvé ça dans un cours. J'ai considéré que la fonction était tellement évidente que je n'ai presque pas réfléchi. Je ne sais pas ce qui m'a pris de la vouloir récursive. Je l'ai corrigée maintenant.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
function factorielle(n:integer):integer;
var fact:integer;
begin
fact:=1;
for i:=2 to n do fact:=fact*i;
factorielle:=fact;
end;

J'ai changé de méthode. Je n'utilise plus de matrice. Mais le principe est toujours le même. A présent, je dis que pour trouver les arrangements de (a b c), il faut placer a dans toutes les positions de tous les arrangements de (b c). A titre d'exemple, toutes les positions possibles de a dans (b c) sont 1, 2 et 3. Comme ça :
abc (a est dans la position 1 de bc)
bac (a est en seconde position)
bca (je pense que vous avez compris...)
J'utilise la commande insert. La commande insert doit être appelée de cette façon :
Insert(chaîne_à_insérer, chaîne_dans_laquelle_on_insère, j) où j est la position à partir de laquelle on insère.
Alors, quand j'utilise insert, je lui donne chaque fois un j différent qui va de 1 jusqu'à dépasser la longueur de la chaîne d'une case exactement.

Tout d'abord, toutes les possibilités avec une chaîne d'un seul caractère : 1 évidement. Ceci est défini et est rentré dans le tableau qui va être le résultat de l'exécution de l'algorithme.
Avec 2 caractères, on doit utiliser le tableau -déjà rempli avec, en réalité, une seule case contenant le dernier caractère de la chaîne sur laquelle on exécute l'algorithme- afin de rendre un tableau contenant toutes les possibilités avec 2 caractères en plaçant le 1er parmi ces deux dans toutes les positions possibles. (longue phrase ... je n'arrive pas à m'exprimer plus clairement)
Avec 3 caractères, on utilise encore le tableau contenant, cette fois, toutes les possibilités avec un caractère de moins. A toutes les possibilités, on ajoute le premier caractère de la chaîne aux différents emplacements possibles et on construit ainsi un nouveau tableau.
Comme le tableau est utilisé pour connaître les possibilités d'ordre inférieur, on ne doit écrire dessus que lorsqu'on finit de l'utiliser. C'est pour ça qu'il est impératif de remplir un tableau temporaire (t2 dans l'algorithme qui va suivre).

Le programme fonctionne. Heureusement que j'ai pensé à la procédure insert. L'algorithme est beaucoup plus facile à implémenter comparé à celui qui comporte les matrices, celui que j'ai envoyé en premier lieu. Cependant, il est moins facile à expliquer !

Le programme demande un entier parce que ça ressemble à l'énoncé de mon dernier test d'algorithmique

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
program a914;
uses wincrt;
type strong=string[6]; table=array[1..720] of strong; {il faut bien 720 :)}
var t,t2:table; i,j,k,c:integer; N:strong;{les string[6] servent à économiser la mémoire, n'est-ce pas ?}
 
 
function factorielle(n:integer):integer;
var fact:integer;
begin
fact:=1;
for i:=2 to n do fact:=fact*i;
factorielle:=fact;
end;
 
 
 
procedure arran(var t:table; N:strong); {strong = string[6]}
var cai:char; ch:strong; t2:table;
begin
if length(N)>1 then
	begin 	
	cai:=N[1]; 
	N:=copy(N,2,length(N));
	arran(t,N);
        c:=1; {c est le compteur du tableau t}
	for i:=1 to factorielle(length(N)) do
            begin
	         	for j:=1 to length(N)+1 do 	
		        	begin
			        ch:=t[i];
	                        insert(cai,ch,j); t2[c]:=ch; c:=c+1;
			        end;
            end;
	for i:=1 to c-1 do t[i]:=t2[i]; 
	end
else
	begin
	t[1]:=N
	end;
 
end;
 
(*$M 42000,12000 *) {ça c'est pour que ça fonctionne avec 6}
BEGIN 
write('donnez un entier   ');
readln(N);
 
writeln('Les possiblilités d''arrangements de "',N,'" sont :');
arran(t,N); for i:=1 to factorielle(length(N)) do write('  ',t[i]);
END.

La directive (*$M 42000,12000 *), je l'ai utilisée comme ça en tatonnant, s'il te plaît, explique-moi ce que c'est en détail.
J'ai toujours envie d'implémenter l'algorithme avec les matrices carrées. Je t'en prie revois-le, d'accord ?

Merci infiniment et bon dimanche à tous !

[droggo]

Fio,

La directive (*$M 42000,12000 *), je l'ai utilisée comme ça en tatonnant, s'il te plaît, explique-moi ce que c'est en détail.

Ça modifie la taille de la mémoire réservée pour le programme.
La 1ère valeur pour la pile, l'autre pour la mémoire globale du programme.

Pourquoi faut-il l'augmenter par rapport aux valeurs par défaut (8192,8192) ?

Ton type table occupe 7*720 = 4320 octets, et tu en as déjà 2 dans tes variables globales, ce qui dépasse le 8192.

Pour la pile : les variables locales à une procédure/fonction sont réservées dans la pile du programme, or ta fonction arran a une variable locale de ce même type table, donc chaque appel à cette procédure occupe un peu plus que cette taille (pour les autres variables, + la place pour passer les paramètres et celle pour l'appel lui-même).
Les appels récursifs vont donc rapidement occuper pas mal de place.

A tout hasard, voici ton code remis en forme (j'ai juste changé la phrase affichée au démarrage du programme, car la tienne prête à confusion, et initialisé la fenêtre pour TPW).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
program a914;
uses
  WinCrt;
 
type
  strong = string[6]; 
  table  = array[1..720] of strong; {il faut bien 720 :)}
var 
  t, t2 : table; 
  i, j, k, c : Integer; 
  N : strong;{les string[6] servent à économiser la mémoire, n'est-ce pas ?}
 
function factorielle(n : Integer): Integer;
var
  i, result : Integer;
begin
  result := 1;
  for i := 2 to n do 
    result := result * i;
  factorielle := result;
end;
 
procedure arran(var t : table; N : strong);
var 
  cai : Char; 
  ch : strong; 
  t2 : table;
begin
  if Length(N) > 1 then
  begin   
    cai := N[1]; 
    N   := Copy(N, 2,Length(N));
    arran(t, N);
    c := 1; {c est le compteur du tableau t}
    for i := 1 to factorielle(Length(N)) do
    begin
      for j := 1 to Length(N) + 1 do 
      begin
        ch := t[i];
        Insert(cai, ch, j); 
        t2[c] := ch; 
        c := c + 1;
      end;
    end;
    for i := 1 to c - 1 do 
      t[i] := t2[i]; 
  end
  else
  begin
    t[1] := N
  end;
end;
 
(*$M 42000,12000 *) {ça c'est pour que ça fonctionne avec 6}
begin
  InitWinCrt;
 
  Write('donnez une chaine (longueur <= 6)   ');
  Readln(N);
 
  Writeln('Les possiblilités d''arrangements de "', N, '" sont :');
  arran(t, N); 
  for i := 1 to factorielle(Length(N)) do 
    Write('  ', t[i]);
 
  Readln;
 
  DoneWinCrt;
end.

Je trouve très cureiux, car très inhabituel, d'utiliser N pour le nom d'une chaine de caractères.
Ce n'est bien sûr pas interdit, mais ce genre de nom est le plus souvent utilisé pour un entier, ce qui ne rend pas la lecture du code immédiate (en particulier avec ton code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
write('donnez un entier   ');
readln(N);

belle confusion pour l'utilisateur, et pour le lecteur du code ).

Pour ton implémentation avec des matrices, je n'ai pas trop le temps, mais je vais essayer de jeter un coup d'oeil.

[katrena99]

RE!

Je trouve très cureiux, car très inhabituel, d'utiliser N pour le nom d'une chaine de caractères.
Ce n'est bien sûr pas interdit, mais ce genre de nom est le plus souvent utilisé pour un entier, ce qui ne rend pas la lecture du code immédiate (en particulier avec ton code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
write('donnez un entier   ');
readln(N);

belle confusion pour l'utilisateur, et pour le lecteur du code )

Entièrement d'accord et ce n'est pas dans mes habitudes à moi non plus. D'ailleurs je m'en suis excusé.

Le programme demande un entier parce que ça ressemble à l'énoncé de mon dernier test d'algorithmique.

Ç'aurait été mieux de le changer !

Juste après le Begin du programme principal, tu utilises InitWinCrt et juste avant la fin DoneWinCrt. Pourquoi ?

Maintenant que cette solution fonctionne, j'aimerais en connaître d'autres pour "Énumérer les arrangements possibles" avec tous les caractères d'une chaîne dans une chaîne de même taille.

Merci!