2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – user9660 Dec 26 '14 at 8:14
  • $\begingroup$ Have a look at Subsets. $\endgroup$ – b.gates.you.know.what Dec 26 '14 at 8:28
  • $\begingroup$ You can break up your set S into a partition S_1 and S_2 with S_1 /union S_2 = S. Calculate the permutations of S_i and from that build up the total number of permutations chunk by chunk. $\endgroup$ – mgamer Dec 26 '14 at 10:01
  • 1
    $\begingroup$ Closely related or possible duplicate: (1283) $\endgroup$ – Mr.Wizard Dec 26 '14 at 22:12
1
$\begingroup$

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"}}*)
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.