CODEWITHSUNDEEP
functional-programmingpattern-matchingocamlpermutation
Addem
Addem

Reputation: 3919

Generating all permutations in a functional language

As an academic exercise I'm trying to generate all possible permutations of a list using the OCaml language, and can't use a for-loop. I can use variables, recursion, pattern-matching, and if-else controls.

Here's what I'm thinking so far: Since I can use recursion, if I want to generate all 6 permutations of the list [1;2;3] then I could pattern-match with h::t where h is 1 and t is [2;3], and suppose that I have all permutations of [2;3]. Then I want to loop through all of these permutations of [2;3] inserting 1 in every possible coordinate: 0, 1, and 2. So for instance with [2;3] I want to generate [1;2;3] and [2;1;3] and [2;3;1], and then for [3;2] I want to generate [1;3;2] and [3;1;2] and [3;2;1].

However there are some obvious problems. One is that I need to tell the computer, with these tools, how to do insertion--but I figured that out already. I also need to "loop" over all the smaller permutations, and then loop over all their coordinates, something I'm not allowed to do. That's where I'm stuck.

Here's what I've done:

(* This successfully does insertion of v into l at pos.*)
let rec insert_at_i (v: int) (l: int list) (pos: int) : int list =
  begin match (l, pos) with
    | (_, 0) -> v::l 
    | ([], _) -> failwith "invalid insert_at_i"
    | (h::t, _) -> h::(insert_at_i v t (pos - 1))
  end

(* This finds the length of a list.*)
let rec len (l: int list) : int =
  begin match l with
    | [] -> 0
    | h::t -> (1 + (len t))
  end

(* Here I'm trying to take a value like 1 and a list like [2;3] and 
generate the list of all lists where 1 is inserted somewhere.  Since I 
can't loop, I tried thinking of a way to pattern-match, but it's not 
working out.  I tried to make extra parameters for basically keeping 
track of the recursion's results as I go, but I'm running into the 
problem that in a functional language like this, variables can't be re-
written with their side-effects stored, so to speak. *)
let rec insert_ith_at_i (v: int) (l: int list) (pos: int) (sofar: int list list): int list list =
  if (l = []) then [[v]]
  else if (pos > (len l)) then sofar
  else (insert_ith_at_i v l (pos + 1) )

Any guidance or hits are appreciated.

Upvotes: 3

Views: 1764

Answers (1)

Pierre G.
Pierre G.

Reputation: 4425

Here is a solution - I define first some helper function :

let ( ^^ ) e ll = List.map (fun x -> e::x) ll

This function add one element to every list contained in a list : 

1 ^^ [[2; 3]; [3; 2]]  gives : [[1; 2; 3]; [1; 3; 2]]

Then the permut function :

let rec permut l r =  /* l : left, r right */
    match r with 
    | [] -> [[]]
    | [x] -> x ^^ (permut [] l)
    | x::t -> let s = permut (x::l) t in 
              (x ^^ (permut [] (l@t))) @ s;;

 permut [] [1;2;3];

The algorithm runs as follows :

  • pick the first element 'x',
  • compute all the permutations one the remaining elements
  • add x to each computed permutation
  • park this element in the 'left' list
  • pick the second element
  • compute the permutation on the other elements : the first ones hold in the left list, the remaining element of the 't' list ... and so on.

Upvotes: 3

Related Questions