A permutation p₁,p₂,...,p_n of 1,2,...,n is even (resp. odd) if it can be returned to the original order 1,2,...,n using an even (resp. odd) number of interchanges of pairs of elements. It is known that every permutation is either even or odd (and therefore not both).

The sign, or signum (for those who want to be fancy), of a permutation is +1 for an even permutation and -1 for an odd permutation.

You are given the integer n and the array p initialized to the integer values p[1]=p₁, p[2]=p₂, ..., p[n]=p_n which are guaranteed to be a permutation of 1,2,...,n. What algorithm would you advocate for determining the sign of the permutation? You need not preserve the original contents of p.

(In reply to No Subject by And Or)

If I read your code right, you are only considering fixed points.  However, 2143 and 4123 both have no fixed points but have opposite signs. The number of one-element orbits does not determine the sign, but ... .

Posted by Richard on 2006-08-07 12:57:18