Version française
Home     About     Download     Resources     Contact us    
Browse thread
Permutations
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ 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 reverse-lexicographic 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...