[Algorithms] Generating the ith permutation of N elements

[Yannick L. <yan...@ub...>]

I'm looking for a way to generate the ith permutation of N elements, at approximately O(N) cost.

All algorithms I've seen need the (i-1)th permutation in order to derive the ith permutation from it (e.g. they work incrementally).

I would just like to give it a number in the range

0 <= i < N!

and it would spit out the ith permutation, without requiring to compute the ones that come before it (which would be O(N!) ).

Is that possible ?

Any pointers appreciated.

Yannick