Discussion :

[matovitch]

Bonjour à tous,
Je viens ici pour poster un code maple, qui je l'espère sera utile.
Petite histoire : Il y a quelque temps j'ai découvert le problème du voyageur de commerce (sans formaliser : étant donné un certain nombre de ville trouver le cycle le plus court les reliant).
Ma première impulsion a été de coder un programme qui teste toutes les permutations possibles.
Je me suis alors aperçu qu'engendrer les permutations d'un ensemble à n éléments, ça n'était pas évident du tout.

J'ai testé tout d'abord la méthode récursive décrite ici :http://fr.wikipedia.org/wiki/Algorithme_r%C3%A9cursif

Mais l'algorithme a une complexité horrible 1!+2!+...+n! (et la série harmonique diverge,donc pas en O(n!))
Puis j'ai trouvé l'algorithme de Rosen : http://www.merriampark.com/perm.htm
que je n'ai pas réussi à adapter en maple.

Alors j'ai cherché un algo et (bonheur ) j'en ai trouvé 2.

Le premier qui engendre les permutations avec des "renversement" .
(le renversement de ceci c'est icec)
Le second engendre les permutations avec des transpositions. Et ce de manière systématique.

Les codes sont horribles (ni indentés ni commentés) j'en ai conscience.

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
reverse:=proc(list,p)
local lst,i,n;
n:=nops(list);
lst:=list[1..n-p-1];
for i from 0 to p do
lst:=[op(lst),list[n-i]];
od;
print lst
return lst
end proc;
 
permute:=proc(n)
local k,a,i,j,mem,memem;
a:=[seq(s,s=1..n)];
print(a);
a:=reverse(a,1);
i:=2;
mem:=[1];
while i<>n do
a:=reverse(a,i);
mem:=[op(mem),i];
i:=i+1;
memem:=mem;
for j from 1 to i-2 do
memem:=[op(memem),op(mem)];
for k from 1 to nops(mem) do
a:=reverse(a,mem[k]);
od;
od;
for k from 1 to nops(mem)-1 do
a:=reverse(a,mem[k]);
memem:=[op(memem),mem[k]];
od;
mem:=memem;
od;
end proc;

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
swap:=proc(list,p,i)
local lst,k,l;
k:=nops(list)-i;
l:=k+p;
lst:=list;
lst[k]:=list[l];
lst[l]:=list[k];
print(lst);
return lst
end proc;
 
permute:=proc(n)
local i,j,k,mem,memem,a;
a:=[seq(s,s=1..n)];
print(a);
i:=1;
mem:=[];
while i<n-1 do
memem:=mem;
for j from 0 to i-1 do
a:=swap(a,i-j,i);
memem:=[op(memem),[i-j,i]];
memem:=[op(memem),op(mem)];
for k from 1 to nops(mem) do
a:=swap(a,mem[k][1],mem[k][2]);
od;
od;
mem:=memem;
i:=i+1;
memem:=mem;
for j from 0 to i-1 do
a:=swap(a,i,i);
memem:=[op(memem),[i,i]];
memem:=[op(memem),op(mem)];
for k from 1 to nops(mem) do
a:=swap(a,mem[k][1],mem[k][2]);
od;
od;
mem:=memem;
i:=i+1;
od;
if type(n,even) then
for j from 0 to i-1 do
a:=swap(a,i-j,i);
for k from 1 to nops(mem) do
a:=swap(a,mem[k][1],mem[k][2]);
od;
od;
fi;
end proc;

Le deuxième est le plus rapide (n! transpositions et 1 test logique si n est pair).L'algorithme de Rosen est-il plus rapide ?

Je n'ai pas prouvé les algorithmes donc si quelqu'un est motivé, je suis à sa disposition. (ça fonctionne de 1 à 4 puis j'ai testé avec des permutations aléatoires au delà).

Merci de votre lecture.

[Nemerle]

Petite remarque: il suffit de prendre les transpositions t(i,i+1) permutant 2 éléments consécutifs pour générer tout le groupe des permutations.

[matovitch]

Oui, mais comment effectuer n! de ces transpositions pour engendrer toutes les permutations ?
On peut affirmer que tout nombre s'écrit comme produit de nombres premiers mais cela
ne donne pas l'algorithme de décomposition.

[Nemerle]

en utilisant le fait (et en notant Ti la transposition i / i+1) que les permutations "sont" l'ensemble des mots générés par l'alphabet T1...T(n-1), en incluant les 2 relations

- TiTj=TjTi si |i-j|>1
- TiTiTi=TjTiTj

Par exemple, pas la peine de déterminer T1T3 et T3T1, le 1ier suffit.

[Onimaru]

Salut, je crois que cela peut t'aider, voci deux algorithmes récursifs :

Les algorithmes donnent toutes les permutations possibles sans répétition
des valeurs du tableau 'Combinaison' qui contient les éléments à permuter.

Le premier algorithme affiche ces combinaisons en ordre :

Code Delphi :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
procedure Combinaisons(var Vecteur, Combinaison : Tab; Niveau: integer);
var I : integer;
begin
 if Length(Vecteur) = 0 then
  AfficherVecteur(Combinaison)
 else
  for I := 0 to High(Vecteur) do
   begin
    Combinaison[Niveau] := Vecteur[I];
    Supprimer(Vecteur, I);
    Combinaisons(Vecteur, Combinaison, Niveau + 1);
    Inserer(Vecteur, I, Combinaison[Niveau])
   end
end;

---------------------------------------------------------------------

Le deuxième affiche toutes les combinaisons mais par en ordre (une sorte de code de Gray) mais plus rapide :

Code Delphi :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
procedure Combinaisons(var Vecteur : Tab; Niveau: integer);
var I : integer;
begin
 if Niveau = High(Vecteur) + 1 then
  AfficherVecteur(Vecteur)
 else
  for I := Niveau to High(Vecteur) do
   begin
    Permuter(Vecteur, Niveau, I);
    Combinaisons(Vecteur, Niveau + 1);
    Permuter(Vecteur, Niveau, I)
   end
end;