# Challenge: Creating Compilable Permutations Function

As Mathematica's implemented Permuations function is not compilable I tried to write my very own Permutations implementation, called PermutationsNew, which I want to compile later on. Unfortunately the only implementation I came up with so far uses recursive programming and looks like this:

PermutationsInternal = Function[{list, listfixed}, If[Length[list] == 1, Join[listfixed, list], Table[PermutationsInternal[Drop[list, {i}], Append[listfixed, list[[i]]]], {i, Length[list]}] ]];
PermutationsNew[list_] := Flatten[PermutationsInternal[list, {}], Length[list] - 2]


The implementation seems to work fine, but because of the recursive structure I cannot come up with any approach that can be compiled, because mathematica has trouble compiling the lists encountered in PermutationsInternal.

Does anybody have an idea on how to compile the above approach or can offer me an idea for a different compilable solution?

-
What is your use case? With permutations there's a danger of running out of memory before running out of time ... –  Szabolcs Mar 29 at 17:17
I mean, Permutations returns a packed array, so it is memory efficient. ByteCount@Permutations[Range[11]] // AbsoluteTiming gives 1.8 seconds and 3.5 GB on my machine. There's clearly not enough memory to go to $n=12$ and 1.8 seconds is still not that slow for a one-time computation. –  Szabolcs Mar 29 at 17:22
memory usage should not be a problem, the lists I need to permute usually do not contain more than 8 items, but the permutation process would be part of a highly optimized and compiled function that in return has to be applied frequently in the computation process –  Wizard Mar 29 at 17:24
In that case how about precomputing permutations once, perm = Permutations@Range[4], then applying these precomputed permutations to your actual list, as in {a,b,c,d}[[#]]& /@ perm? This application can be done using a compiled function much more easily. If your list has the same integers as Range[1,n], then the permuted lists will be equivalent to perm, except in a different order. So this will probably make sense if your list has other numbers than {1,2,3,4} in some order. –  Szabolcs Mar 29 at 17:28
I think that's a good solution. I will try this out soon, but I do not see why it should not work. Thank you very much. –  Wizard Mar 29 at 20:07