Re: [pygame] more maths wanted...

[Magnus Lie Hetland <magnus@hetland.org>]

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