[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

*To*: Arnd Zapletal <a_zapletal@web.de>*Subject*: Re: [pygame] more maths wanted...*From*: Magnus Lie Hetland <magnus@hetland.org>*Date*: Mon, 10 Nov 2003 21:41:21 +0100*Cc*: PyGame Users <pygame-users@seul.org>*Delivered-to*: archiver@seul.org*Delivered-to*: pygame-users-outgoing@seul.org*Delivered-to*: pygame-users@seul.org*Delivery-date*: Mon, 10 Nov 2003 15:41:45 -0500*In-reply-to*: <20031110150918.2747f973.a_zapletal@web.de>*Mail-followup-to*: Arnd Zapletal <a_zapletal@web.de>,PyGame Users <pygame-users@seul.org>*References*: <20031110042609.701d13be.a_zapletal@web.de> <20031110130113.GB28756@idi.ntnu.no> <20031110150918.2747f973.a_zapletal@web.de>*Reply-to*: pygame-users@seul.org*Sender*: owner-pygame-users@seul.org*User-agent*: Mutt/1.4i

Arnd Zapletal <a_zapletal@web.de>: > > On Mon, 10 Nov 2003 14:01:13 +0100 > Magnus Lie Hetland <magnus@hetland.org> wrote: > > > I don't know of any extensions, but -- what algorithm are you using? > > If you're using a recursive one, perhaps a non-recursive one might > > help? (I've got the relevant pseudocode -- at least for all the > > permutations -- if you're interested.) > > Thanx, I *am* interested Note that the standard algorithm (The Steinhaus-Johnson-Trotter [1] algorithm) does not generate the permutations in lexicographic order; rather, each pair of permutations in the sequence differ by one swap of adjacent elements. I have the full pseudocode in a book on constructive combinatorics at work; I wasn't able to find any useful description online at the moment. What I *did* find, however, was a rather cool paper from 2003(!) by Jie Gao and Dianjun Wang [2] on a two new methods for permutation generation. Rather surprising, since the S-J-T-algorithm is from the early sixties... I guess constructive combinatorics isn't quite dead ;) The algorithms are pretty cool -- one of them (the Level Algorithm) can be used to (in O(n) time, with n being the number of elements) generate any numbered iteration of the sequence. (E.g. "give me permutation number 42".) The other one, according to the authors, is "close to optimal" in that it uses very few operations. BTW: I guess you could probably use the Level Algorithm together with Numeric/numarray to get some speedups, as the positions of each element are simply calculated with div/mod based on the permutation number (i.e. index in an array of permutations)... [1] http://www.nist.gov/dads/HTML/SteinhausJohnsonTrotter.html [2] http://arxiv.org/pdf/cs.DS/0306025 -- Magnus Lie Hetland "In this house we obey the laws of http://hetland.org thermodynamics!" Homer Simpson

**References**:**[pygame] more maths wanted...***From:*Arnd Zapletal <a_zapletal@web.de>

**Re: [pygame] more maths wanted...***From:*Magnus Lie Hetland <magnus@hetland.org>

- Prev by Author:
**Re: [pygame] more maths wanted...** - Next by Author:
**[pygame] overlay menu on mplayer** - Previous by thread:
**Re: [pygame] more maths wanted...** - Next by thread:
**[pygame] Fwd: Plug: Game Programming with Python Book** - Index(es):