1
|
6666 Views
|
4 Replies
|
2 Total Likes
View groups...
Share
GROUPS:

# Permutations, one at a time?

Posted 11 years ago
 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 11 years ago
 This function which generates the next permutation in lexicographical order may be useful.
Posted 11 years ago
 Beautiful! Thank you, Ilian, and thank you, Nayuki Minase.
Posted 11 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 11 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}