# Permutations[Range[12]] produces an error instead of a list

This input:

Permutations[Range[12]]


Results in this (error) output:

Permutations::outsize:
The result of evaluating Permutations[{1,2,3,4,5,6,7,8,9,10,11,12}]
would be a packed array with 5748019200 elements, but the number of elements
in a packed array must be a machine integer. >>


That number (5748019200) is interesting, because it's exactly 12 times 12! (that's factorial, not exclamation point)

Presumably, Mathematica is trying to store all 12! length 12 lists in a single monolithic array. I can imagine this failing.

Usually, Mathematica shields me from these types of problems. For example, I had no trouble calculating 12*12!.

My intention is to Select some elements from this list, so I don't need to have every permutation in memory at once.

Question: Is there a different way to generate the permutations that avoids this problem?

-
Run the same code on a 64-bit machine ;-) Seriously though, it is possible to iterate over permutations but I'm not sure if the algorithm is implemented directly in Mathematica. –  David Z Feb 4 '12 at 3:28
@David It doesn't work on a 64-bit machine either. Harold: Apparently the maximum size of a packed array is 2^31-1. This is a huge array: a 2^31 - 1-element packed array of machine integers (i.e. assuming the most efficient storage possible) would take up 8 GB of contiguous memory. You need to have a lot of memory in your computer to be able to store such an array (definitely much more than 8 GB because of the contiguous memory block requirement) –  Szabolcs Feb 4 '12 at 20:13
@Szabolcs 8 GB is quite a bit of memory, but modern operating systems, on top of which the Mathematica kernel runs, allocate memory in page-sized chunks (most commonly 4 kilobytes each), and (virtual) memory region which appears contiguous to the Mathematica kernel doesn't need any special attention on the operating system level. It just requires lots of RAM, or swap space. Contiguous memory problem existed roughly up to mid-nineties, but not really afterwards. –  kirma Oct 2 '14 at 16:18

Combinatorica has the function NextPermutation which allows you to iterate over the permutations. There may be ways of generating a smaller subset if you have more information about what you are looking for.

-
On that note: the algorithms in Combinatorica are based on old FORTRAN routines discussed in this book; OP might want to take a look at the book and see what other strategies might be appropriate for his circumstances. –  Guess who it is. Feb 4 '12 at 3:48
@J.M., that book looks to be a tremendous resource. I'm glad I asked this question now. –  Harold Feb 4 '12 at 4:52
@Harold note, the functionality in Combinatorica  is being slowly folded into the kernel functions. So, loading it will give a warning message to that effect, but NextPermutation doesn't (yet?) seem to have been moved over. –  rcollyer Feb 4 '12 at 4:55
@J.M. Thanks a lot for the link to that book. Looks excellent –  TomD Feb 4 '12 at 9:34
@rcollyer NextPermutation has in a way already been moved over: you can use GroupElements to emulate it. –  Teake Nutma Oct 1 '14 at 13:20

Consider than the permutations of {1, 2, 3, 4, 5} are each of the permutations of {1, 2, 3, 4} with 5 inserted at each possible place. One can therefore examine the permutations of {1, 2, 3, 4, 5} in blocks like this:

p4 = Permutations@Range@4;

Table[
ReplaceList[x, {h___, t___} :> {h, 5, t}],
{x, p4}
]


For example, making a certain selection:

Table[
Select[
ReplaceList[x, {h___, t___} :> {h, 5, t}],
# + #2 - #3*#4/#5 > 7 & @@ # &
],
{x, p4}
]


The same can be applied to the permutations of Range@12.

-

Since Mathematica 8 it is possible generate the elements of any group one by one with GroupElements. Here's for example a randomly chosen element of the permutation group on 20 elements:

GroupElements[SymmetricGroup[20], {10^6 + 1}]

{Cycles[{{11, 13, 19}, {12, 18, 17, 16}, {15, 20}}]}


The result is immediately; there's no need to build up the full group of $20! \approx 2.4 \cdot 10^{18}$ elements. We can use this to scan over the permutations of a given list without generating them all at once:

ScanPermutations[function_, list_] /; Length[list] <= 8 :=
Scan[function, Permutations @ list];

ScanPermutations[function_, list_] :=
Do[
Scan[
function @ Permute[list, #] &,
GroupElements[
SymmetricGroup @ Length @ list,
Range[8! * (i - 1) + 1, 8! * i]
]
],
{i, Length[list]! / 8!}
];


The code splits up the permutations in blocks of $8! = 40320$ whenever the given list has more than 8 elements. This is about ten times faster than calling GroupElements to generate just one permutation at a time.

Printing e.g. the permutations of {1,2,3} can now be done as follows:

ScanPermutations[Print, {1,2,3}]

{1,2,3}
{1,3,2}
{2,1,3}
{3,1,2}
{2,3,1}
{3,2,1}


Going one step further, we may use Reap and Sow to select permutations that match a given criterion:

SelectPermutations[list_, crit_] :=
First @ Last @ Reap @ ScanPermutations[
If[crit @ #, Sow @ #] &,
list
];


And finally, here's a small example that puts the above in action. It selects the even permutations of {1,2,3}:

SelectPermutations[{1, 2, 3}, Signature[#] === 1 &]

{{1, 2, 3}, {2, 3, 1}, {3, 1, 2}}

-
I appreciate this late answer. This technique looks promising and has several attractive properties when compared with some of the answers above. Neat stuff. Thanks! –  Harold Oct 1 '14 at 22:41
+1 for a Necromancer badge. –  Mr.Wizard Oct 3 '14 at 19:34

Well from computational point of view, if you wanted the whole list or some part of it then the size of output would be the main problem.

Assuming plaintext output is used ... by my rough estimation it would take over 225 GB (gigabytes) to store the whole list on a disk. Furthermore it would take about 4 days to compute them all on this laptop.

You need data like:

filename = "f://out.txt";
seed = Range[12];
size = 10;


Recursive method call like:

seed = MPermutations[seed, size, filename]


Other useful lines:

FilePrint[filename]
DeleteFile[filename]


This is an example of what MPermutations could look like if flat file output is used. It computes next count number of permutations of list, prints them in filename and returns the last element.

MPermutations[list_, count_Integer, filename_String] := Module[
{n = 1, current = list},
OpenAppend[filename];
While[
n < count, current = NextPermutation[current];
n++;
Write[filename, current]];
Close[filename];
current]


Return result is needed to make recursive method call possible. Recomputing that line will add next size amount of results to file (assuming that data is in a different cell).

-

### Migrated from here

Mathematica is quite likely to be slow at generating permutations. Here is a Java-based approach. It is based on Java reloader and this nice Java code, which I slightly extended with a getNextMultiple method.

So, load the Java reloader first (run the code from that post). Then, execute the following:

JCompileLoad @ "
import java.util.Arrays;

public class PermutationGenerator {
private int[] array;
private int firstNum;

public PermutationGenerator(int n, int firstNum_) {
if (n < 1) {
throw new IllegalArgumentException(\"The n must be min. 1\");
}
firstNum = firstNum_;
array = new int[n];
reset();
}

public void reset() {
for (int i = 0; i < array.length; i++) {
array[i] = i + firstNum;
}
}

public boolean hasMore() {
for (int i = 1; i < array.length; i++) {
end = end && array[i] < array[i-1];
}
return !end;
}

public int[] getNext() {

return array;
}

int temp;
int j = array.length - 2;
int k = array.length - 1;

// Find largest index j with a[j] < a[j+1]

for (;array[j] > array[j+1]; j--);

// Find index k such that a[k] is smallest integer
// greater than a[j] to the right of a[j]

for (;array[j] > array[k]; k--);

// Interchange a[j] and a[k]

temp = array[k];
array[k] = array[j];
array[j] = temp;

// Put tail end of permutation after jth position in increasing order

int r = array.length - 1;
int s = j + 1;

while (r > s) {
temp = array[s];
array[s++] = array[r];
array[r--] = temp;
}

return array;
} // getNext()

public int[][] getNextMultiple(int n) {
int[][] result = new int[n][];
int i = 0;
int len = array.length;
while(hasMore()){
if(i>=n) break;
result[i++] = Arrays.copyOf(getNext(), len);
}
if(i == n){ return result;}
int[][] truncated = new int[i][];
for(int j=0;j<i;j++){
truncated[j] = result[j];
}
return truncated;
}

// For testing of the PermutationGenerator class
public static void main(String[] args) {
PermutationGenerator pg = new PermutationGenerator(3, 1);

while (pg.hasMore()) {
int[] temp =  pg.getNext();
for (int i = 0; i < temp.length; i++) {
System.out.print(temp[i] + \" \");
}
System.out.println();
}
}

}";


Now, we can try things. Create the permutation generator:

gen = JavaNew["PermutationGenerator", 14, 1]


Generate first 5 permutations:

gen@getNextMultiple[10]

(*
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14},
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 13},
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 12, 14},
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 12},
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 12, 13}}
*)


Let's get more serious. On my machine, I do generate 5 million permutations per second (including the data transfer time):

ctr = 0;
gen@reset[]
While[(nxt = gen@getNextMultiple[10000]) =!= {} && ctr < 5*10^6,
ctr += Length[nxt]
]; // AbsoluteTiming
ctr

(* {1.040131, Null} *)

(* 5000000 *)


This means that you'll need a few hours to process them all - I only count the time to generate them:

14!/(5*10^6*3600) // N

(* 4.84324 *)


In fact, following halirutan's argument, if we just increment a counter on the top-level, it will take longer than generating permutations:

testctr = 0;
Do[testctr++, {5*10^6}] // AbsoluteTiming

(* {2.361853, Null} *)


But because we generate permutations in large batches, there is some chance that you could write a compiled (and possibly parallelized) function to process them also in batches, and that one may be much faster.

Still, hours, not years ). But of course, I agree with halirutan, that if your function which you plan to apply to permutations is any intensive computationally, this won't help you. So, the goal of my post was to show how to reduce the overhead of permutation generation, only. Whether or not this will be useful will entirely depend on what sort of function you will apply to them.

-