# Need to create a function to generate all permutations of Range[$n$] [duplicate]

Basically I need a function that takes a list and gives all the possible permutations of it. The reason I can't use Permutations is that I have to apply another program that will score each permutation separately, based on certain criteria, and Permutations[Range[14]] gives entirely too much data.

The function has to work for a list Range[int] up to int = 14, each permutation has to include all the members of the original list with no repeats, and the function has to produce all possible permutations.

I will appreciate any help: I'm very stuck.

-

## marked as duplicate by Mr.Wizard♦Apr 15 '14 at 3:13

Look at the Conbinatorica package. You can generate the permutations one at a time to score using its functions. –  rasher Apr 15 '14 at 1:21
14! is a rather large number, so I understand why you might not want to store all the permutations in memory. However, even if you accomplish your goal of generating the permutations one-by-one, how long do you think it will take to score more than 87 billion lists of 14 integers? –  m_goldberg Apr 15 '14 at 1:50
Note to all posters: please take the time to look for duplicates before you answer. This question was almost certainly asked before, and finding a duplicate was easy. –  Mr.Wizard Apr 15 '14 at 3:15
Related: (9537), (21584) –  Mr.Wizard Apr 15 '14 at 3:20
@Mr.Wizard This may look like a duplicate, but the emphasis here is on how one can make this work, not on the mere fact that the straight-forward use of Permutations will blow up the memory. –  Leonid Shifrin Apr 15 '14 at 14:53

One way to go through all possible permutations is the NextPermutation function from the Combinatorica package. But one word of advice: Did you really think through what you are trying to do?

Let's say you just want to loop through 14! iterations and you will do nothing more than increment a counter and go to the next permutation. Incrementing a counter is one of the most basic operations and should take almost no time at all. Let's see how far you come in 1 minute:

Needs["Combinatorica"];

i = 0;
perm = Range[14];
TimeConstrained[Do[i++; perm = NextPermutation[perm], {14!}], 60]


After this minute, I have finished 0.003% (i/14!*100.0) of the 14! iterations. It took a minute iterating over nothing to accomplish 0.003%!! Now assume you have a task which needs at least a small amount of time. For instance 1/1000 of a second. With this amount of work per cycle, you will need

14!*1/1000./60/60/24
(* 1009.01 *)


1000 days until you are done. Almost 3 years.

You should probably reconsider the importance of your task. If it is for instance a computation you need for your phd, you will probably run out of money before you have your results.

-
Precisely why I recommended the Conbinatorica package (third-party, out of San Quentin): threatens data with a shiv, things happen quickly... –  rasher Apr 15 '14 at 2:10
@rasher I'm not concerned about how quick you can create the list of permutations, but what he will actually do with it. If his algorithm working on each permutation is only a tiny bit non-trivial, the overall run-time will climb ridiculously fast. –  halirutan Apr 15 '14 at 3:37
I think the joke got lost in translation... in any case, the sports syndicate's money is safe, by the time the OP gets results, it will be next season. –  rasher Apr 15 '14 at 3:38
@rasher Ah, sorry. I'm very bad with insider jokes when they are in a different language. You would have to explain this in detail to make me understand. I guess this is not worth the effort :-) –  halirutan Apr 15 '14 at 3:50

If you're merely interested in finding permutations with a good 'score', and wish to avoid storing huge lists of permutations in memory, consider the simulated annealing algorithm:

https://en.wikipedia.org/wiki/Simulated_annealing

For this application, the algorithm involves repeatedly swapping two elements of the list to form new candidate solutions. If the score of the new list is better, it is accepted as the new solution. If the score of the new list is worse, it may still be accepted with a nonzero probability. The probability of a worse list being accepted decreases with higher score differential, and also with time (as the object 'cools', there is less 'energy' available to escape local minima).

The output is a 'pretty good' solution, but there's no guarantee it will be the best.

-