0
$\begingroup$

When I try

Permutations[Range[1, 12]]; // AbsoluteTiming

I get

{53.6949, Null}

and with Permutations[Range[1, 14]]; // AbsoluteTiming the computer takes hours.

Is this true in general, or is it a slow function in Mathematica?

Is there any very fast way of getting the permutations of the list $ \{1, 2, \dots, n\} $? Perhaps with parallel processing?

|improve this question
$\endgroup$
  • $\begingroup$ It grows like a factorial, which gets big really quickly. Look at Length[Permutations[Range[1, #]]] & /@ Range[10] $\endgroup$ – bill s Sep 5 at 13:55
  • $\begingroup$ But so big it takes a fast processor hours to compute? Even up to 14? $\endgroup$ – Alexander Kartun-Giles Sep 5 at 13:56
  • $\begingroup$ @bills It is not like a factorial --- it just is the factorial. $\endgroup$ – Αλέξανδρος Ζεγγ Sep 5 at 13:58
  • $\begingroup$ I would say that is growing a LOT like a factorial. $\endgroup$ – bill s Sep 5 at 14:00
  • 4
    $\begingroup$ "But so big it takes a fast processor hours to compute?" en.wikipedia.org/wiki/Combinatorial_explosion Yes. Exponential complexity is like hitting a wall. You can compute it up to n, but not n+1. Maybe you can go to n+1 if you wait 5-10 years for faster computers, but not to n+2. This problem is worse than exponential (factorial) both in computation time and in memory requirements. $\endgroup$ – Szabolcs Sep 5 at 16:32
2
$\begingroup$

You can check the memory usage:

ByteCount[Permutations[Range[11]]]

You see this is 3.5GB. for 12 it will be ~42GB. I guess you have less memory than that. So it will start to do swapping memory to your hard-drive, with all kinds of performance issues.

Make sure to have $HistoryLength = 1 such that not all the outputs are stored for a long time and fill up your memory.

What do you want to do with this huge list?

|improve this answer
$\endgroup$
  • $\begingroup$ It’s about listing all colourings a 2xn grid $\endgroup$ – Alexander Kartun-Giles Sep 5 at 14:44
1
$\begingroup$

It grows like the factorial function. Indeed:

Length[Permutations[Range[1, #]]] & /@ Range[10] == Factorial[Range[10]]

True

So 

Factorial[14]
87178291200
|improve this answer
$\endgroup$
  • $\begingroup$ So Mathematica is fast, and the process is just meant to take hours. But can you use parallel processing to speed it up? $\endgroup$ – Alexander Kartun-Giles Sep 5 at 14:00
  • $\begingroup$ Where are you going to store those 87178291200 lists? $\endgroup$ – bill s Sep 5 at 14:02
  • $\begingroup$ How many bits per list element? I suppose this is hundreds of gigabits? $\endgroup$ – Alexander Kartun-Giles Sep 5 at 14:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.