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?
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.