gdalgorithms-list

[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

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
>

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

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

[Danny K. <dr...@we...>]

>  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).#
>
As far as I know there isn't a standard order for permutations and so there
isn't such a thing as 'the' i'th permutation. Am I wrong? Or are you just
looking for a consistent order rather than a standard one?

Danny

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

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

Yes any consistent order will do.

Yannick

From: Danny Kodicek [mailto:dr...@we...]
Sent: 1 juin 2010 14:48
To: Game Development Algorithms
Subject: Re: [Algorithms] Generating the ith permutation of N elements


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).#
As far as I know there isn't a standard order for permutations and so there isn't such a thing as 'the' i'th permutation. Am I wrong? Or are you just looking for a consistent order rather than a standard one?

Danny

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

[Tim A. <tim...@gm...>]

If I understand the problem correctly, a multi-base number conversion
algorithm is what you are looking for. That is, you have number (the
number of the permutation), and you have a number of sub-elements with
a number of possible values each. This is the same problem as
decimal-to-binary conversion, or extracting radices from a decimal
number. I have written a wee-small python script (below) to
demonstrate the algorithm I would use, which is O(n) over the number
of bases.

Let me know if this is helpful to you, or if this isn't the problem
you are trying to solve.

Cheers,
--Tim A.
Co-Founder/Engineer, Final Form Games
http://www.finalformgames.com/

###
import math

#some example bases:
#bases = [10, 10, 10, 10, 10, 10, 10, 10, 10] # number -> decimal radices
#bases = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] # decimal ->
16-bit binary
#bases = [365, 24, 60, 60] # seconds -> day/hour/minute/second

bases = [10, 10, 10, 10, 10, 10, 10, 10, 10]
which = 128 # number of the permutation you want

perm = []
accum = 1
x = which
for i in reversed(range(0, len(bases))):
 s = bases[i]
 n = math.ceil((x / accum) % s)
 perm.insert(0, n)
 x -= n * accum
 accum *= s

print("Permutation #" + str(int(which)) + " is " + str(perm))
###

On Tue, Jun 1, 2010 at 3:34 PM, Yannick Letourneau
<yan...@ub...> wrote:
> Yes any consistent order will do.
>
>
>
> Yannick
>
>
>
> From: Danny Kodicek [mailto:dr...@we...]
> Sent: 1 juin 2010 14:48
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Generating the ith permutation of N elements
>
>
>
>
>
> 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).#
>
> As far as I know there isn't a standard order for permutations and so there
> isn't such a thing as 'the' i'th permutation. Am I wrong? Or are you just
> looking for a consistent order rather than a standard one?
>
>
>
> Danny
>
>
>
> ------------------------------------------------------------------------------
>
>
> _______________________________________________
> 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
>

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

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

Yeah actually I think combining your decomposition to Robin Green's inversion to reconstruct the permutation from the decomposition will do the trick.

Thanks all for you input.

-----Original Message-----
From: Tim Ambrogi [mailto:tim...@gm...]
Sent: 1 juin 2010 16:59
To: Game Development Algorithms
Subject: Re: [Algorithms] Generating the ith permutation of N elements

If I understand the problem correctly, a multi-base number conversion
algorithm is what you are looking for. That is, you have number (the
number of the permutation), and you have a number of sub-elements with
a number of possible values each. This is the same problem as
decimal-to-binary conversion, or extracting radices from a decimal
number. I have written a wee-small python script (below) to
demonstrate the algorithm I would use, which is O(n) over the number
of bases.

Let me know if this is helpful to you, or if this isn't the problem
you are trying to solve.

Cheers,
--Tim A.
Co-Founder/Engineer, Final Form Games
http://www.finalformgames.com/

###
import math

#some example bases:
#bases = [10, 10, 10, 10, 10, 10, 10, 10, 10] # number -> decimal radices
#bases = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] # decimal ->
16-bit binary
#bases = [365, 24, 60, 60] # seconds -> day/hour/minute/second

bases = [10, 10, 10, 10, 10, 10, 10, 10, 10]
which = 128 # number of the permutation you want

perm = []
accum = 1
x = which
for i in reversed(range(0, len(bases))):
 s = bases[i]
 n = math.ceil((x / accum) % s)
 perm.insert(0, n)
 x -= n * accum
 accum *= s

print("Permutation #" + str(int(which)) + " is " + str(perm))
###

On Tue, Jun 1, 2010 at 3:34 PM, Yannick Letourneau
<yan...@ub...> wrote:
> Yes any consistent order will do.
>
>
>
> Yannick
>
>
>
> From: Danny Kodicek [mailto:dr...@we...]
> Sent: 1 juin 2010 14:48
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Generating the ith permutation of N elements
>
>
>
>
>
> 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).#
>
> As far as I know there isn't a standard order for permutations and so there
> isn't such a thing as 'the' i'th permutation. Am I wrong? Or are you just
> looking for a consistent order rather than a standard one?
>
>
>
> Danny
>
>
>
> ------------------------------------------------------------------------------
>
>
> _______________________________________________
> 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
>

------------------------------------------------------------------------------

_______________________________________________
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

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

[<chr...@pl...>]

Yannick Letourneau wrote:

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

http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica
http://realtimecollisiondetection.net/blog/