Algorithme de permutation

**Arthur Rainbow** · 13/01/2010, 03h03

Bonjour.

Je suis aussi en train de chercher à énumérer les permutations afin d'executer une fonction sur chaque permutation de [0..n], comme dans la discussion http://www.developpez.net/forums/d50...e-permutation/

Dans l'idéal, il me faudrait la liste, mais c'est ingérable en mémoire. A la place, ce serait bien d'être capable de générer rapidement la ième permutation si on avait généré la liste, ou encore, à partir de la (i-1)ème de généré la (ième).

Or ça me parait assez difficile à faire avec vos méthode récursives avec des "prints" quelqu'un aurait une idée, je ne trouve rien ?
Ou alors, à la limite, dans un langage fonctionnel je peux ajouter aux générateur des permutations le fait qu'il doit prendre une fonction qui prend la permutation en argument, mais comme mon code est actuellement en C++, je suis peu chaud pour tout réécrire.

Envoyé par acx01b

une permutation d'un ensemble E:
c'est un n-upplet qui commence par x1 suivi d'une permutation de E privé de x1
ou un n-upplet qui commence par x2 suivi d'une permutation de E privé de x2
ou un n-upplet qui commence par x3 suivi d'une permutation de E privé de x3
...
ou un n-upplet qui commence par xn suivi d'une permutation de E privé de xn

où x1, x2, x3 .... xn sont les éléments de E

Si on veut travailler comme ça, il y a moyen d'être plus efficace.
Je donne le code en oCaml, car c'est plus naturel en fonctionnel.

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
 
let rec fold_left f accu l =
  match l with
    [] -> accu
  | a::l -> fold_left f (f accu a l) l
 
let permut l f acc=
  let rec aux l1 l2 acc tmp=
    match (l1,l2) with
      |    [],[]->f tmp acc
      | _,_->  let (acc,_)=
      fold_left (fun (acc, l2) elt l1 ->(aux l1 l2 acc (elt::tmp), elt::l2 ))
        (acc, l2) l1 
    in let (acc,_)=
      fold_left (fun (acc, l1) elt l2 ->(aux l2 l1 acc (elt::tmp), elt::l1 ))
        (acc, l1) l2 
    in acc
  in aux [] l [] []
 
let list_permut l=
  permut l (fun a b-> a::b) []

On doit redéfinir fold_left car la fonction a aussi besoin de connaitre la queue de la liste.

On choisit un élément qu'on met en fin de liste, puis on itére sur la liste sans cet élément. La grosse différence c'est que comme on le retire effectivement de la liste, il ne sera pas reparcouru, contrairement à ce qui se fait avec un tableau.
On est forcé deux passer recursivement deux listes, car sans ça il faudrait faire un "append" entre les deux listes à passer en argument, ce qui est couteux.

Dans les deux cas on est clairement en O(n^n), et je n'arrive pas à savoir si on gagne asymptotiquement. Ce qui est sur c'est qu'on passe d'un temps en
O(n+n^2+n^3+...+n^n)=O(n(1+n(1+n(...(1+n)...)))) n fois à quelque chose en O(n+n(n-1)+n(n-1)(n-2)+...+n!)=O(n*(1+(n-1)*(1+(n-2)*(....(1+1)...)))), ce qui semble à priori être un gain.

Si vous avez des remarques à faire, je serai ravi, pour le moment, je rame.