Generating a permutation of elements in chunks - Mathematica Stack Exchange most recent 30 from mathematica.stackexchange.com 2019-08-19T09:10:27Z https://mathematica.stackexchange.com/feeds/question/69678 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://mathematica.stackexchange.com/q/69678 2 Generating a permutation of elements in chunks TaperedStick https://mathematica.stackexchange.com/users/23387 2014-12-26T07:20:54Z 2014-12-26T21:42:30Z <p>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? </p> <p>Consider that (WARNING: DO NOT RUN! --- Will generate a list with 13! = 6,227,020,800 entries!)</p> <pre><code>Permutations[{"t1","t2","t3","t4","t5","t6","t7","t8","t9","t10","t11","t12","t13"}] </code></pre> <p>Will obviously not be storable on a standard personal computer.</p> <p>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?</p> <p>For example:</p> <pre><code>smallEx=Permutations[{"t1","t2","t3"}]; </code></pre> <p>Gives the output:</p> <pre><code>{{"t1", "t2", "t3"}, {"t1", "t3", "t2"}, {"t2", "t1", "t3"}, {"t2", "t3", "t1"}, {"t3", "t1", "t2"}, {"t3", "t2", "t1"}}; </code></pre> <p>I was hoping for some way to write a function like:</p> <pre><code>PermutationChunk[{"t1","t2","t3"}, {3,5}] </code></pre> <p>That in this case, with \$(n_1,n_2)\$ = {3,5}, would return:</p> <pre><code>{{"t2", "t1", "t3"}, {"t2", "t3", "t1"}, {"t3", "t1", "t2"}} </code></pre> <p>Or a single permutation for:</p> <pre><code>PermutationChunk[{"t1","t2","t3"}, {2,2}] </code></pre> <p>Out:</p> <pre><code>{"t1", "t3", "t2"} </code></pre> <p>Is this possible?</p> https://mathematica.stackexchange.com/questions/69678/-/69686#69686 1 Answer by Hubble07 for Generating a permutation of elements in chunks Hubble07 https://mathematica.stackexchange.com/users/7009 2014-12-26T13:06:48Z 2014-12-26T13:06:48Z <p>I found the relevant mathematics <a href="https://math.stackexchange.com/questions/60742/finding-the-n-th-lexicographic-permutation-of-a-string">here</a> and below is my attempt at coding it in mma.</p> <pre><code>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) &amp;&amp; q &gt;= 0 &amp;&amp; 0 &lt; r &lt;= 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] ]; </code></pre> <p>The above code gives the \$k^{th}\$ permutation of the list which then can be used over a range.</p> <pre><code> permutationChunk[list_, min_, max_] := main[list, #] &amp; /@ Range[min, max] </code></pre> <p>It works for the case you mentioned</p> <pre><code> 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"}}*) </code></pre> https://mathematica.stackexchange.com/questions/69678/-/69708#69708 0 Answer by Wouter for Generating a permutation of elements in chunks Wouter https://mathematica.stackexchange.com/users/7680 2014-12-26T21:42:30Z 2014-12-26T21:42:30Z <p>The required functionality exists in the Combinatorica Package, loaded using Needs["Combinatorica`"].</p> <p>The 3,000,000,000 th permutation of Range is<br> <code>NthPermutation[3*10^9, Range]</code><br> <code>{7, 4, 2, 11, 3, 12, 1, 10, 5, 6, 8, 9, 13}</code><br> and the inverse operation is<br> <code>RankPermutation[%]</code><br> <code>3000000000</code><br> Remark that the identity permutation has rank zero, not one.</p>