Re: [Algorithms] Generating the ith permutation of N elements

[<pad...@ob...>]

One mapping is to convert your index i to base-e for e elements.
That's surjective/onto.
But IIR discrete maths there's more than one definition of ith permutation

 

On 01 June 2010 at 18:57 Yannick Letourneau <yan...@ub...>
wrote:

> 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