# Permutations, one at a time?

Posted 9 years ago
5163 Views
|
4 Replies
|
2 Total Likes
|
 For large lists (where you don't have enough memory to store the entire array), I used to do this with the Combinatorica NthPermutation, now apparently UnrankPermutation. And it worked fine with lists composed of all different elements where I knew exactly how many permutations there were in total. That is not the case with the kind of lists with which I am now working: much larger versions of {-1,-1,-1,1,1,1} or {-1,-1,-1,0,1,1,1} to give examples for lengths 6 and 7. How many permutations are there and, more importantly, how do I step through them all, one at a time? An acquaintance who is working on the same problem in Sage was able to accomplish this simply by deleting .list() from the program line for p in Permutations(T).list():. Wow!
4 Replies
Sort By:
Posted 9 years ago
 This function which generates the next permutation in lexicographical order may be useful.
Posted 9 years ago
 Beautiful! Thank you, Ilian, and thank you, Nayuki Minase.
Posted 9 years ago
 In[15]:= Length[Union[Table[UnrankPermutation[i, list7], {i, 140}]]]Out[15]= 20Only 20 of the first 140 UnrankPermutations are unique. The rest are duplicates. I need to be able to generate all 140 unique permutations in no more than 140 steps.
Posted 9 years ago
 Hello,UnrankPermutation seems to work well! First, the number of permutations:nrOfPermutations[set__] := Length[set]!/(Count[set, -1]! Count[set, 0]! Count[set, 1]!)Thenlist7 = {-1, -1, -1, 0, 1, 1, 1};list100 = RandomInteger[{-1, 1}, 100];In[11]:= nrOfPermutations@list7nrOfPermutations@list100Out[11]= 140Out[12]= 3133814355737177511825520127334957139222939200Finally In[13]:= UnrankPermutation[50, list7] Out[13]= {-1, -1, 1, -1, 1, 0, 1} In[14]:= UnrankPermutation[5378, list100] Out[14]= {1, 0, -1, 1, 0, 0, 1, -1, 1, -1, 0, 1, -1, -1, 1, -1, 0, 1, \ 1, 0, 0, 1, 0, -1, -1, -1, -1, -1, 0, 0, 1, 0, 1, 0, -1, 1, 1, -1, \ -1, -1, 1, 0, -1, 1, 0, -1, -1, 0, -1, 0, -1, -1, 1, 0, -1, -1, 1, 1, \ 1, -1, 1, 0, -1, 0, 1, -1, -1, -1, -1, 0, 0, -1, 1, 1, 0, 1, 0, -1, \ -1, 0, 0, 1, 0, 0, 1, 1, -1, 1, 1, -1, 0, 0, -1, 1, -1, 1, 0, -1, 0,   1}