* Fred lunnon <fred.lunnon@gmail.com> [Dec 18. 2006 09:30]:
A slick way to generate permutations is via a sequence of adjacent transpositions [usually credited to Trotter and Johnson, though some authors claim it predates these publications].
e.g. Knuth, see his preprints for vol.4, lookup "plain changes".
Most implementations seem to rely on maintaining at least one global array, say s_k = +1,-1 according to whether symbol k is currently transposing rightwards, leftwards along the array of n symbols;
Revisiting this recently, I noticed that an array is unnecessary: all that is required is a single binary digit containing the parity of the current permutation; then the other parities required --- of the partial permutations of symbols k,...,n --- can be efficiently deduced as required.
Can you elaborate? I am big fan of Trotter's algorithm (in fact several implementations are given in pp.233-238 of my scribblings online at http://www.jjj.de/fxt/#fxtbook ).
But it does not seem easy to extirpate this final bit, without committing the algorithm to an O(n log n) computation at every call in order to find the parity, essentially by sorting the permutation.
Is there an O(n) algorithm for parity of a permutation? If not, why not?
Follow the cycles, as mentioned in other reply. (but note this needs a tag array, so this is O(n) in both time and space).
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
best regards, jj