Permutations, one at a time?

Questions
,
1

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!

2

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}
3 
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.

4

This function which generates the next permutation in lexicographical order may be useful.

5

Beautiful! Thank you, Ilian, and thank you, Nayuki Minase.