3
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ Look at the Conbinatorica package. You can generate the permutations one at a time to score using its functions. $\endgroup$ Commented Apr 15, 2014 at 1:21
  • $\begingroup$ 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? $\endgroup$ Commented Apr 15, 2014 at 1:50
  • $\begingroup$ 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. $\endgroup$ Commented Apr 15, 2014 at 3:15
  • $\begingroup$ Related: (9537), (21584) $\endgroup$ Commented Apr 15, 2014 at 3:20
  • $\begingroup$ @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. $\endgroup$ Commented Apr 15, 2014 at 14:53

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Precisely why I recommended the Conbinatorica package (third-party, out of San Quentin): threatens data with a shiv, things happen quickly... $\endgroup$ Commented Apr 15, 2014 at 2:10
  • $\begingroup$ @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. $\endgroup$ Commented Apr 15, 2014 at 3:37
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 15, 2014 at 3:38
  • $\begingroup$ @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 :-) $\endgroup$ Commented Apr 15, 2014 at 3:50
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.