Por que o NextPermutation é lento?

Question

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

Quero economizar memória, tentei NextPermutation, mas está meio lento, por quê?

Answer 1

Você precisa de UnrankPermutation

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

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

Eu escrevi uma takePermutationfunção, talvez você esteja interessado

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, nulo}
{0,777691, nulo}
verdadeiro