Standard ML permutations

Question

I am working on a function to the permutations for all values in a list.

Here is what I have so far:

//MY ROTATE FUNCTION

fun rotate e [] = [[e]]
| rotate e (x::xs)= (e::x::xs)::(List.map (fn l => x::l) (rotate e xs));

//MY CURRENT PERMUTATION FUNCTION

fun perm [] = []
| perm (x::xs) = List.concat(List.map (fn l => (rotate x xs)) xs) @ perm xs;

OUTPUT:

- perm [1,2,3];

val it = [[1,2,3],[2,1,3],[2,3,1],[1,2,3],[2,1,3],[2,3,1],[2,3],[3,2]]

The output should be something like [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. As you can see I am missing something here. I believe the issue is my 3 is not being passed to rotate as rotate 3 [1,2] is what I am missing from my code along with two 2 element lists being here for some reason.

How can I correct my perm function to show the output correctly? Any help no matter how big or small would help me a lot.

Answer 1

I don't think that the rotate approach is the one you'll want to take. Rather, as Shivindap describes here, a good way to do this sort of this is to pull the first element from the argument list, and append it to all permutations of the tail. Rinse and repeat this for every element of the list, and you'll end up with all the permutations.

You'll find an in depth explanation of this approach here. For code samples in ML, you could also check this out.

Best of luck to you!

Answer 2

Here is a simple fix for your attempted solution. You were nearly there.

fun interleave x [] = [[x]]
| interleave x (h::t) =
    (x::h::t)::(List.map(fn l => h::l) (interleave x t))

fun permute nil = [[]]
| permute (h::t) = List.concat( List.map (fn l => interleave h l) (permute t))