Generating a permutation of elements in chunks

Question

Is there a way for me to generate a list of permutations in "chunks" such that I needn't store everything on RAM all at once?

Consider that (WARNING: DO NOT RUN! --- Will generate a list with 13! = 6,227,020,800 entries!)

Permutations[{"t1","t2","t3","t4","t5","t6","t7","t8","t9","t10","t11","t12","t13"}]

Will obviously not be storable on a standard personal computer.

However, is there a way for me to ask Mathematica for the a "chunk" of permutations with indices $n_1$ through $n_2$ where, hypothetically if we had the output for Permutations above, $n_1$ would be the index of the first element in the chunk we ask for and $n_2$ would be the index of the last element in the chunk we ask for?

For example:

smallEx=Permutations[{"t1","t2","t3"}];

Gives the output:

{{"t1", "t2", "t3"}, {"t1", "t3", "t2"}, {"t2", "t1", "t3"}, {"t2", "t3", "t1"}, {"t3", "t1", "t2"}, {"t3", "t2", "t1"}};

I was hoping for some way to write a function like:

PermutationChunk[{"t1","t2","t3"}, {3,5}]

That in this case, with $(n_1,n_2)$ = {3,5}, would return:

{{"t2", "t1", "t3"}, {"t2", "t3", "t1"}, {"t3", "t1", "t2"}}

Or a single permutation for:

PermutationChunk[{"t1","t2","t3"}, {2,2}]

Out:

{"t1", "t3", "t2"}

Is this possible?

Answer 1

I found the relevant mathematics here and below is my attempt at coding it in mma.

main[list_, pos_] := 
Module[{f, r, len, fr1, fr2, index, finalresult},

len = (Length[list] - 1);
finalresult = {};
f[num_, fac_] := Module[{res},
 res = 
  Solve[(num == q*fac! + r) && q >= 0 && 0 < r <= fac!, {q, r}, 
   Integers];
 finalresult = Join[{finalresult, res[[1, 1, 2]] + 1}];
 res[[1, 2, 2]]
 ];
 FoldList[f, pos, Range[len, 0, -1]];
 index = Flatten[finalresult];

 fr1 = {};
 r[l_, ind_] := Module[{},
 fr2 = Take[l, {ind}];
 fr1 = Join[{fr1, fr2}];
 Sort[Drop[l, {ind}]]
 ];
FoldList[r, list, index];
 Flatten[fr1]
 ];

The above code gives the $k^{th}$ permutation of the list which then can be used over a range.

 permutationChunk[list_, min_, max_] := 
 main[list, #] & /@ Range[min, max]

It works for the case you mentioned

 permutationChunk[{"t1", "t2", "t3"}, 3, 5]
 (*{{"t2", "t1", "t3"}, {"t2", "t3", "t1"}, {"t3", "t1", "t2"}}*)

permutationChunk[{"t1", "t2", "t3", "t4", "t5", "t6", "t7", "t8", 
  "t9", "t10", "t11", "t12", "t13"}, 100000000, 100000000]
  (*{{"t1", "t12", "t4", "t5", "t6", "t11", "t13", "t9", "t2", "t7", "t3",
  "t8", "t10"}}*)

Answer 2

The required functionality exists in the Combinatorica Package, loaded using Needs["Combinatorica`"].

The 3,000,000,000 th permutation of Range[13] is
NthPermutation[3*10^9, Range[13]]
{7, 4, 2, 11, 3, 12, 1, 10, 5, 6, 8, 9, 13}
and the inverse operation is
RankPermutation[%]
3000000000
Remark that the identity permutation has rank zero, not one.