Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by Mr.Wizard Apr 15 at 3:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Look at the Conbinatorica package. You can generate the permutations one at a time to score using its functions. –  rasher Apr 15 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 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 at 3:15
    
Related: (9537), (21584) –  Mr.Wizard Apr 15 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 at 14:53

2 Answers 2

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.

share|improve this answer
    
Precisely why I recommended the *Con*binatorica package (third-party, out of San Quentin): threatens data with a shiv, things happen quickly... –  rasher Apr 15 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 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 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 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.

share|improve this answer

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