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

Question

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.

Answer 1

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.

Answer 2

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.