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