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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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).