In this post, I will talk about a common approach for generating all permutations, its complexity, and how big the argument list can be that makes the stack overflow using OCaml. I borrow some pictures and work from typeocaml.
The insert-into-all-positions solution
Let’s assume that we have a set of all permutations for a set of 3 elements. Thus totally
there are 6 permutations. For example, let 3 elements be [1;2;3], then 6 permutations
are [1;2;3], [2;1;3], [2;3;1], [1;3;2], [3;1;2], and [3;2;1].
So now what if we put a new element, say 4, into the set of 4 elements [1;2;3;4]? What
we need to do is combining the new element 4 into the previous set of permutations to
generate a new set of permutations.
Let’s see how a new element is inserted into a permutation. Consider a permutation of 3
elements [1;2;3], there are 4 possible positions (before 1, 2, 3, and after 3)
to insert 4 as shown in the figure.
Therefore, with 6 previous permutations we have totally \(4 * 6 = 24\) new permutations
if we insert the new element 4.
Code
The implementation can be done by the following two functions. The insert_all_positions
function inserts a new element given a set of permutations. The permutations function
recursively generates all permuations. If the number of elements is 0 or 1, then there
is only 1 permutation. Here is the Gist.
let insert_all_positions x l =
let rec aux prev acc l =
match l with
| [] -> (prev @ [x]) :: acc |> List.rev
| hd::tl as l -> aux (prev @ [hd]) ((prev @ [x] @ l) :: acc) tl
in aux [] [] l;;
let rec permutation l =
match l with
| [] -> []
| hd::[] -> [[hd]]
| hd::tl -> List.fold_left (fun acc p -> acc @ insert_all_positions hd p) [] (permutation tl);;
Complexity
The complexity depends on the number of permuations which is \(n!\)
(n is the number of elements). Assume that the complexity of insert a new element to
a permuation takes 1 time unit, thus for a permuation consisting of m elements, it
takes \((m + 1)\) time units. Therefore for each recursive call, we have the complexity
\(T(m) = m * T(m - 1)\). The complexity of the algorithm should be
\(T(n) = n * T(n - 1)\) \(= n * (n - 1) * T(n - 2)\) \(= ...\) \(= n * (n-1) * (n - 2) * ... * 2 * T(1) = n!\)
Stack overflow
When I run the code above with OCaml version 4.02.1, stack overflow occurs likely with the number of elements is 9. For example,
permutation [1;2;3;4;5;6;7;8;9];;
Stack overflow during evaluation (looping recursion?).
Dynamic permutations
One interesting way to deal with big number of elements is generating one permutation at each time. One can employ the Johnson Trotter algorithm to generate a different permutation each time. I will talk about this algorithm in a next post.