# Permutations of $\{1, 2, \dots, n\}$ [duplicate]

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?

• It grows like a factorial, which gets big really quickly. Look at Length[Permutations[Range[1, #]]] & /@ Range – bill s Sep 5 '19 at 13:55
• But so big it takes a fast processor hours to compute? Even up to 14? – apkg Sep 5 '19 at 13:56
• @bills It is not like a factorial --- it just is the factorial. – Αλέξανδρος Ζεγγ Sep 5 '19 at 13:58
• I would say that is growing a LOT like a factorial. – bill s Sep 5 '19 at 14:00
• "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. – Szabolcs Sep 5 '19 at 16:32

You can check the memory usage:

ByteCount[Permutations[Range]]

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?

• It’s about listing all colourings a 2xn grid – apkg Sep 5 '19 at 14:44

It grows like the factorial function. Indeed:

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

True


So

Factorial
87178291200

• So Mathematica is fast, and the process is just meant to take hours. But can you use parallel processing to speed it up? – apkg Sep 5 '19 at 14:00
• Where are you going to store those 87178291200 lists? – bill s Sep 5 '19 at 14:02
• How many bits per list element? I suppose this is hundreds of gigabits? – apkg Sep 5 '19 at 14:02