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 re: What I would NOT advocate by Old Original Oskar!)

There are several other ways besides "sorting" and what one means by "sorting" needs to be carefully stated in order to genuinely specify an algorithm.  Just any old sort is clearly not what was sought here, nor did the problem state in any way that sorting was necessarily sought at all. In algorithms, the devil is in the details.  Your "solution" gives no details and seems mostly to be a statement based on the novel view that giving a definition of a term somehow locks in an algorithm.  There are several equivalent but very different definitions of a permutations's sign -- giving one of them for clarity and completeness of the problem's statement does not obligate anyone to slavishly use that one for constructing their algorithm. Since you have Journeyman rank, you can now view the unapproved solution and see what a variety of algorithms is possible.  I am sorry that you didn't really see the intent of the problem, but I don't think that was my fault. Your contributions here so far have not been very useful, but perhaps with some thought and effort you could yet give a useful solution in the form of a genuine algorithm specification.

Posted by Richard on 2006-08-07 16:31:55