User Tools

Site Tools


permutations

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

permutations [2015/10/08 15:20] (current)
Line 1: Line 1:
 +====== Permutations ======
 +
 +1. define the function ''​map f l''​ that applies the function ''​f''​ to each element of the list ''​l''​
 +<code ocaml>
 +map : ('a -> 'b) -> 'a list -> 'b list
 +</​code>​
 +
 +2. Define the function ''​shuffle x l''​ that inserts the element ''​x''​ at each position inside the list ''​l''​. For instance, ''​shuffle 1 [2;​3]''​ evaluates to [ [1;2;3]; [2;1;3]; [2;3;1] ]
 + 
 +<code ocaml>
 +shuffle : 'a -> 'a list -> 'a list list
 +</​code>​
 +
 +3. define the function ''​flatten l''​ that transforms a list of lists of elements of type T into a list of elements of type T. For instance, ''​flatten [ [1;2]; [3;4;5] ]''​ evaluates to ''​[1;​2;​3;​4;​5]''​.
 +
 +<code ocaml>
 +flatten : 'a list list -> 'a list
 +</​code>​
 +
 +4. Define the function ''​perm l''​ that evaluates to the list of all the permutations of the elements of the list ''​l''​. For instance, ''​perm [1;​2;​3]''​ evaluates to ''​[ [1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1] ]''​.
 +
 +<code ocaml>
 +perm : 'a list -> 'a list list
 +</​code>​
 +
 +
 +===== Solution =====
 +
 +<code ocaml>
 +let rec map f l = match l with
 +  [] -> []
 +| x::xl -> f(x) :: map f xl;;
 +
 +let rec shuffle y l = match l with
 +  [] -> [[y]]
 +| x::xl -> (y::x::xl) :: (map (fun l -> x::l) (shuffle y xl));;
 +
 +let rec flatten ll = match ll with
 +  [] -> []
 +| x::xll -> x @ (flatten xll);;
 +
 +let rec perm l = match l with
 +  [] -> [[]]
 +| x::xl -> flatten (map (shuffle x) (perm xl));;
 +</​code>​
  
permutations.txt ยท Last modified: 2015/10/08 15:20 (external edit)