Message Boards Message Boards

1
|
6020 Views
|
4 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Permutations, one at a time?

Posted 10 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!
POSTED BY: Hans Havermann
4 Replies
This function which generates the next permutation in lexicographical order may be useful.
POSTED BY: Ilian Gachevski
Posted 10 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]!)
Then
list7 = {-1, -1, -1, 0, 1, 1, 1};
list100 = RandomInteger[{-1, 1}, 100];

In[11]:= nrOfPermutations@list7
nrOfPermutations@list100

Out[11]= 140
Out[12]= 3133814355737177511825520127334957139222939200
Finally
 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}
POSTED BY: Hans Milton
In[15]:= Length[Union[Table[UnrankPermutation[i, list7], {i, 140}]]]
Out[15]= 20
Only 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 BY: Hans Havermann
Beautiful! Thank you, Ilian, and thank you, Nayuki Minase.
POSTED BY: Hans Havermann
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract