All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Sign of a Permutation (Posted on 2006-08-05) Difficulty: 3 of 5
A permutation p1,p2,...,pn 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]=p1, p[2]=p2, ..., p[n]=pn 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.

See The Solution Submitted by Richard    
Rating: 3.2000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
No Subject | Comment 6 of 11 |
Nice solution, Bractals! I am J ;).
A simple explanation of how it works is: Every position in the array is visited once and whenever its visited the element in this position is placed at its right position. Hence it sorts the list. Since it uses the swap operation only once per position that it visits, the total swaps are utmost n (if an element is already in its position no swap is used). Hence the complexity is linear. Cool algo. Hats off.
So, can we improve the given soln? I think yes :). Here it goes.
   I = 1
   SIGNUM = N%2 ? 1 : -1
   while I++, I < N
     if P(I) = I then
       SIGNUM = -SIGNUM
ENDIF
ENDWHILE

  Posted by And Or on 2006-08-07 10:46:16
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information