5
$\begingroup$
<< Combinatorica`
Permutations[Range[0, 9]][[1000000]] // AbsoluteTiming
Nest[NextPermutation, Range[0, 9], 1*^6 - 1] // AbsoluteTiming

I want to save memory, so I tried NextPermutation ,but it's kind of slow, why?

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ If you look in the documentation tp Nest, then you understand the iteration is executed 999999 times. $\endgroup$
    – user64494
    Sep 16, 2020 at 6:42
  • 5
    $\begingroup$ Rather than repeatedly using NextPermutation, you could use PermutationFromIndex to get the 999999+1th lexicographic permutation straight away and very quickly. ResourceFunction["PermutationFromIndex"][10^6, 10] - 1 gives {2, 7, 8, 3, 9, 1, 5, 4, 6, 0}. $\endgroup$
    – flinty
    Sep 16, 2020 at 10:14

1 Answer 1

8
$\begingroup$

You need UnrankPermutation

<< Combinatorica`;
UnrankPermutation[10^6 - 1, Range[0, 9]] // AbsoluteTiming

{0.0001106, {2, 7, 8, 3, 9, 1, 5, 4, 6, 0}}

I wrote a takePermutation function, maybe you are interested

Quiet[<< Combinatorica`];

Clear[cf, takePermutation];
cf = Compile[{{l, _Integer, 1}, {num, _Integer}},
   Module[{res = l, n = Length @ l, i, j, nl, tmp},
    Table[
     nl = res;
     i = n - 1;
     While[nl[[i]] > nl[[i + 1]], i--];
     j = n;
     While[nl[[j]] < nl[[i]], j--];
     tmp = nl[[i]];
     nl[[i]] = nl[[j]];
     nl[[j]] = tmp;
     res = nl[[Join[Range[i], Range[n, i + 1, -1]]]]
     , {num}]
    ], CompilationTarget -> "C", RuntimeOptions -> "Speed"
   ];

takePermutation[l_?VectorQ, i1_Integer, i2_Integer] := 
  If[i1 == 1, Join[{l}, cf[UnrankPermutation[i1 - 1, l], i2 - i1]], 
    cf[UnrankPermutation[i1 - 2, l], i2 - i1 + 1]] /; 0 < i1 <= i2;

r1 = takePermutation[Range[11], 11! - 10^5, 11!]; // AbsoluteTiming
r2 = Take[Permutations[Range[11]], {11! - 10^5, 11!}]; // AbsoluteTiming
r1 == r2

{0.0396038, Null}
{0.777691, Null}
True

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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