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