2

Let say I have a sequence [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and I want to retrieve the 4th element of the 1,000,000th permutation of this list.

I know how to compute the 1,000,000th permutation of the sequence using the algorithm explained here : Finding the n-th lexicographic permutation of a string

This permutation is [2 7 8 3 9 1 5 4 6 0], and so the 4th element is 3.

But is there a faster way to find "3", I mean except stopping computing the permutation after the 4th element?

fbparis
  • 153
  • 4

1 Answers1

4

I have extensive experience with this and as far as I can tell there's no direct way to go to the $i$th element without computation. But look at it in perspective. The computation is not so bad. You can precompute factorials, then it's just a few operations to get an arbitrary index. Granted, the amount of operations increases with the index, but it's a very small number. It's negligible unless you're doing it a vast number of times.

If you are doing it a vast number of times, I'd say to avoid computing the element at all if that's possible with your application. If you need to do something like exchange adjacent elements or determine which is larger, that can be done in constant time without backing out the actual elements.

Matt Samuel
  • 58,164
  • Thanks a lot for your answer. Unfortunately I can't avoid computing this and I do it very frequently. Also I can't cache the permutations (256! is a huge number). If you're curious I'm using this for a home made cipher, source code here https://gist.github.com/fbparis/a5749da7efa88183976ff8ebb1174faf – fbparis Jan 02 '19 at 03:49
  • @fbparis One example where I never backed out a single element of the permutations is https://codereview.stackexchange.com/q/182610/155626 it probably won't help you much since it's so opaque. Also, for my application $n=16$ was the goal, which I never did end up achieving. $n=256$ will never, ever, be feasible for my problem, not if you turned the whole planet into a giant computer. – Matt Samuel Jan 02 '19 at 03:53
  • If you want to retrieve the full permutation, this algorithm is pretty fast and will work fine with n=256 or greater http://code.activestate.com/recipes/126037-getting-nth-permutation-of-a-sequence/ – fbparis Jan 02 '19 at 04:09
  • @fbparis Oh, the part of my application that's infeasible for $n=256$ is the fact that the main loop has $256!$ iterations, as I'm summing over every permutation. Only a few operations per iteration, but I already estimated it would take $100$ days for $n=16$. – Matt Samuel Jan 02 '19 at 04:12
  • @fbparis Also have to store intermediate results. – Matt Samuel Jan 02 '19 at 04:12