Permutations

mtikilia <mt99@d...>
 Michel Quercia
 Mattias Waldau
 mtikilia <mt99@d...>
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Michel Quercia <michel.quercia@p...> 
Subject:  Re: "ocaml_beginners"::[] Permutations 
Le Wed, 05 Feb 2003 13:48:11 0000 "mtikilia <mt99@d...>" <mt99@d...> écrivit: > This is rather embarassing but I have found myself unable to produce a > function that would give me a list of lists which are all available > permutations of [1;2;3;4;5;6;7;8;9], such that each number occurs only > once. > > Please help. Bits of code would be appreciated. You can use something like this : (* insert x at all positions into l and return the list of results *) let rec insert x l = match l with  [] > [[x]]  a::m > (x::l) :: (List.map (fun y > a::y) (insert x m)) ;; (* list of all permutations of l *) let rec perms l = match l with  a::m > List.flatten (List.map (insert a) (perms m))  _ > [l] ;; # perms [1;2;3];;  : int list list = [[1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]] ... but perms [1;2;3;4;5;6;7;8;9] raises a stack overflow ... OK, some permutation theory now : If p is a permutation of the integers 1..n then you can compute from p the next permutation in lexicographic order, p', with the following algorithm : 1. find the last index i for which p(i) < p(i+1) 2. exchange p(i) with the smallest p(j) such that p(j) > p(i), j=i+1..n 3. reverse the sublist p(i+1)...p(n). example with p = [1;4;3;6;5;2] we get : after step 1 : p(i) = 3 after step 2 : [1;4;5;6;3;2] after step 3 : [1;4;3;2;3;6] = p' (if step 1. fails then p has no lexicographic successor). The following Ocaml code implements a variation on this algorithm (it returns the permutations of 1..n in reverse reverselexicographic order) : (* exchange into l @ [x] @ accu x with the last element of l which is > x *) let rec swap l x accu = match l with  a::b::t when b > x > a :: (swap (b::t) x accu)  a::t > (x::t) @ (a::accu)  _ > failwith "this can't happen" ;; (* permut l m accu computes the permutation p' following p = rev(l)@m, stores it into accu and recalls itself until p has no successor *) let rec permut l m accu = match l,m with  a::_, b::t when a > b > let p = swap l b t in permut [] p (p::accu)  _, b::t > permut (b::l) t accu  _, [] > accu ;; (* build x n accu returns [n; ...; x] @ accu *) let rec build x n accu = if x>n then accu else build (x+1) n (x::accu) ;; (* permutations n returns the list of all permutations of 1..n *) let permutations n = let p = build 1 n [] in permut [] p [p] ;; # permutations 3;;  : int list list = [[1; 2; 3]; [2; 1; 3]; [1; 3; 2]; [3; 1; 2]; [2; 3; 1]; [3; 2; 1]] # List.length(permutations 9);;  : int = 362880 # List.length(permutations 10);;  : int = 3628800 permutations 11 will probably bomb out my little frail computer, I prefer not try ...  Michel Quercia 23 rue de Montchapet, 21000 Dijon http://michel.quercia.free.fr (maths) http://pauillac.inria.fr/~quercia (informatique) mailto:michel.quercia@p...