Perché NextPermutation è lento?

Question

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

Voglio risparmiare memoria, quindi ho provato NextPermutation, ma è un po 'lento, perché?

Answer 1

Hai bisogno di UnrankPermutation

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

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

Ho scritto una takePermutationfunzione, forse ti interessa

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