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.

The sign can be expressed as Product{i <j} [(p[i]-p[j])/(i-j)].  If you don't notice that the result is exactly the same as that given by FK's algorithm in his comment just below, you could go ahead and calculate the factors in floating point and get a result that would no doubt be close to +1 or -1, but could well not be exactly equal to either. Using exact rational arithmetic would give exactly +1 or -1, of course. This is the worst algorithm I know for calculating the sign of a permutation.  I dedicate it to OOO.

For extra credit, figure out as a function of n what the absolute value of the product of all the numerator (or denominator) factors is, and give its value when n=100.

Edited on August 5, 2006, 11:13 pm

Posted by Richard on 2006-08-05 23:05:50