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

[Robin G. <rob...@gm...>]

There is a recursive pattern used to generate each iteration which can
be used to generate the iterations directly. Check out this CS lecture
on permutations:

http://www.math.ust.hk/~mabfchen/Math232/Generating-Permutations.pdf

- Robin Green.


On Tue, Jun 1, 2010 at 9:57 AM, 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
>
> ------------------------------------------------------------------------------
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>