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]. 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. 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? Fred Lunnon
Is there an O(n) algorithm for parity of a permutation? If not, why not?
I found the following O(n) algorithm (coded in Maple) on http://www.math.rwth-aachen.de/mapleAnswers/html/502.html: [As a non-maple-user I assume that ll is the initial permutation, and n is the number of its elements] # parity returns the parity of a permutation of a list of integers # from 1 to n, relative to the standard permutation 1,2,...,n. # It returns 1 for even parity, -1 for odd parity. parity := proc(l::list(posint)) local i,j,ll,n,p; ll := table(l); n := nops(l); i := 1; # i points to the next element to check p := 1; # p keeps track of the parity while i < n do # don't need to check case i=n, it must be right. j := ll[i]; if i <> j then p := -p; ll[i] := ll[j]; ll[j] := j else i := i+1 fi od; p end: enjoy it :-) Christoph
I suppose that algorithm is O(n) if you take as O(1) examining a number with log n bits. --ms -----Original Message----- From: math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com [mailto:math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com]On Behalf Of Pacher Christoph Sent: Sunday, December 17, 2006 11:15 To: math-fun Subject: AW: [math-fun] Permutations
Is there an O(n) algorithm for parity of a permutation? If not, why not?
I found the following O(n) algorithm (coded in Maple) on http://www.math.rwth-aachen.de/mapleAnswers/html/502.html: [As a non-maple-user I assume that ll is the initial permutation, and n is the number of its elements] # parity returns the parity of a permutation of a list of integers # from 1 to n, relative to the standard permutation 1,2,...,n. # It returns 1 for even parity, -1 for odd parity. parity := proc(l::list(posint)) local i,j,ll,n,p; ll := table(l); n := nops(l); i := 1; # i points to the next element to check p := 1; # p keeps track of the parity while i < n do # don't need to check case i=n, it must be right. j := ll[i]; if i <> j then p := -p; ll[i] := ll[j]; ll[j] := j else i := i+1 fi od; p end: enjoy it :-) Christoph
I suppose that algorithm is O(n) if you take as O(1) examining a number with log n bits.
yes, I am thinking this is what Fred had in mind, because he was talking about an O(n log n) algorithm which "essentially sorts the permutation". And sorting integers takes O(n log n) comparisons and swaps of integers (not bits). But I might be completely wrong, Fred? Christoph
Well, if our "atoms" are indeed integers, then it takes O(n) operations to turn a permutation represented as a sequence of n integers into a permutation represented as a list of its cycles, and vice versa. In fact, the algorithm you posted uses the former representation and just follows the cycles (without explicitly generating them) and accumulates the parity. --ms -----Original Message----- From: math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com [mailto:math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com]On Behalf Of Pacher Christoph Sent: Sunday, December 17, 2006 11:48 To: math-fun Subject: AW: [math-fun] Permutations
I suppose that algorithm is O(n) if you take as O(1) examining a number with log n bits.
yes, I am thinking this is what Fred had in mind, because he was talking about an O(n log n) algorithm which "essentially sorts the permutation". And sorting integers takes O(n log n) comparisons and swaps of integers (not bits). But I might be completely wrong, Fred? Christoph
Indeed, I hadn't thought much about representation --- just employed the obvious list of n integers in the range 1,...,n, and costing operations on integers, as you say. Thanks for the algorithm, which I certainly wouldn't have found easily, if at all --- thanks too for Mike Speciner's documentation [noticeably absent from the original, as with most code posted by enthusiasts!]. I realised in the meantime that the adjacent transposition algorithm can be improved from time O(n) to average constant time, at the cost of retaining a counter of permutations previously generated. Its residue mod 2 gives the parity, hence the direction of transpostion; dividing by n...(n-j+1) gives the sub-counter for symbols j,...,n; the final remainder gives the position of the symbol j = k to be transposed. Since k = 1 for all but a fraction 1/n of calls, the average time is now essentially independent of n --- indeed, decreases with it! Fred Lunnon On 12/17/06, Pacher Christoph <Christoph.Pacher@arcs.ac.at> wrote:
I suppose that algorithm is O(n) if you take as O(1) examining a number with log n bits.
yes, I am thinking this is what Fred had in mind, because he was talking about an O(n log n) algorithm which "essentially sorts the permutation". And sorting integers takes O(n log n) comparisons and swaps of integers (not bits).
But I might be completely wrong, Fred?
Christoph
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Surely it depends on how you are representing your permutations. For example, you need O(n log n) bits to represent a permuation of n elements, and you could have the first of those bits be the parity, giving an O(1) algorithm. On the other hand, using the common representation as a list of cycles of length > 1, getting the parity is easy but requires looking at the entire representation, so O(n log n). --ms -----Original Message----- From: math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com [mailto:math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com]On Behalf Of Fred lunnon Sent: Sunday, December 17, 2006 10:57 To: math-fun Subject: [math-fun] Permutations 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]. 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. 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? Fred Lunnon _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* 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
On 12/18/06, Joerg Arndt <arndt@jjj.de> wrote:
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 ).
[fxtbook typo sect 6.9.4.4 --- "An routine" -> "A routine"] I think the best way is probably just to give a (cleaned up) version of the Maple program code, which doesn't use any clever syntax and should be reasonably easy to follow [famous last words]. For somebody who knows the method, the only new idea is the way the parity l of the partial permutation of symbols (k+1,...,n) is continuously updated as the symbol k under consideration increases, until one is found not blocked by smaller symbols along the direction l in which it is currently moving The loop on i which makes the time linear rather than (CAT) constant is avoided in the version I actually use, which just computes everything it needs from the counter, and initialises the array. I'll post that as well for completeness. Sorry about the long lines! Fred Lunnon # Adjacent transposition next permutation generator: # perm = current array of symbols, n = length, cter = name of counter; # result = symbol k transposed; terminate k = n with initial setting restored. # Version for Joerg Arndt utilising only parity of cter; no initialisation; # the loop on i could be avoided using also cter mod n*(n-1)*...*(n+1-k). permute_jj := proc (n, cter, perm) local i,j0,j1,k,l; if n < 2 then k := n else l := (-1)^(eval(cter)-1); # pick up parity j0 := 1; j1 := n; # endpoints of unblocked region k := 1; # current symbol while (perm[j0] = k and l = -1) or (perm[j1] = k and l*(-1)^(j1-j0) = +1) do if perm[j0] = k then j0 := j0+1 # blocked symbol at left end else l := l*(-1)^(j1-j0); j1 := j1-1 fi; # blocked at right k := k+1 od; k := min(n, k); j0 := min(j1, j0); # termination fudge for i from j0 to j1 while perm[i] <> k do od; # locate min unblocked symbol l := l*(-1)^(i+j0); # update symbol direction perm[i] := perm[i+l]; perm[i+l] := k fi; # adjacent transpose cter := eval(cter)+1; # update counter variable in caller k end; # return transposed symbol # Test n := 4: cter := 1: perm := array([seq(i, i = 1..n)]): print(cter, perm); while permute_jj(n, 'cter', perm) < n do print(cter, perm) od: print(cter, perm); # Adjacent transposition permutation generator for n >= 0: constant mean time; # counter set zero to initialise; termination when result = n; user call # cter := 0; perm := array(1..n); while permute('cter', perm) < n do ... od; # initial state restored after termination. permute := proc (cter, perm) local n,i,j0,j1,k,l,cter0,dum; n := op(2, op(2, op(1, perm))); # recover number of symbols if eval(cter) = 0 then # initialise symbol array k := 0; for i from 1 to n do perm[i] := i od; else if n < 2 then k := n+1 else # special cases n = 0,1 cter0 := eval(cter); k := 1; # symbol k currently considered for transposition j0 := 0; j1 := n+1; # limits of smaller symbols blocked at left,right end while cter0 mod(n+1-k) = 0 and k < n do # find smallest unblocked symbol k cter0 := cter0/(n+1-k); k := k+1; if cter0 mod 2 = 0 then j0 := j0+1 else j1 := j1-1 fi od; i := cter0 mod(n+1-k); cter0 := (cter0-i)/(n+1-k); l := 1 - 2*(cter0 mod 2); # direction l of symbol k if l = +1 then i := j0+i else i := j1-i fi; # location i of symbol k dum := perm[i]; perm[i] := perm[i+l]; perm[i+l] := dum; # transpose fi fi; # (know dum = k, except on termination!) cter := eval(cter)+1; # increment counter, called by name k end; # return transposed symbol n := 6; cter := 0; perm := array(1..n); while permute('cter', perm) < n do print(cter, perm) od: print(cter, perm);
participants (4)
-
Fred lunnon -
Joerg Arndt -
Mike Speciner -
Pacher Christoph