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.

  Submitted by Richard    
Rating: 3.2000 (5 votes)
Solution: (Hide)
perm_sign by John Burkardt is an example that can be found online (see it among the collection at http://orion.math.iastate.edu/burkardt/f_src/subset/subset.f90 or see http://www.scs.fsu.edu/~burkardt/math2071/perm_sign.m). A similar method, that, however, avoids explicit searching, is illustrated by the following bc function.
define sign(p[],n) {
auto s,j,q
scale=0
s=1
j=1
#
# get elements back in their home positions
#
while (j < n) {
q=p[j]
if(q==j){
j=j+1 # just move ahead -- no interchange req'd
} else {
p[j]=p[q] # interchange p[j] and p[p[j]]
p[q]=q
s=(-1)*s # and account for the interchange
}
#
# note that q is now in its home position
# whether or not an interchange was required
}
return(s)
}
A somewhat more sophisticated method follows the orbits of elements as they are permuted through cycles. The following bc function illustrates this.
define signum(p[],n) {
auto j,q,r,s,t
scale=0
#
s=1
# follow orbit cycles and tote up signs
for (j=1;j<=n;++j) {
if (p[j] > 0) {
# new cycle, follow it, marking each place
q=j
t=1
while (q > 0) {
r=p[q]
if (r > 0) p[q]=(-1)*r
t=(-1)*t
q=r
}
# factor in contribution of each cycle
s=s*t
}
}
return(s)
}
Lang's Algebra, First Ed. 1965, p. 53, gives an equivalent definition of the sign as simply (-1)m where m=n-number of orbits. Thus the above can be modified to just count the number of orbits and do a little arithmetic at the end, as the following bc function illustrates.
define cycscnt(p[],n) {
auto c,j,q,r,s,m
scale=0
#
s=(-1)
c=0
# count the orbit cycles
for (j=1;j<=n;++j) {
  if (p[j] > 0) {
  # new cycle, follow it, marking each place
  q=j
      while (q > 0) {
      r=p[q]
      if (r > 0) p[q]=(-1)*r
      q=r
      }
  # increment cycle count
  c=c+1
  }
}
m=n-c
if (m%2 == 0) s=1
return(s)
}

Another method counts inversions and leads to the following short bc program.

define inversgn(p[],n) {
auto s,v,i,j
scale=0
#
s=1
v=0
# count inversions
for (i=1;i < n;++i) {
for (j=i+1;j <= n;++j) {
if (p[i] > p[j]) v=v+1
}
}
if (v%2 != 0) s=(-1)
return(s)
}

And one more: Those with a sufficient background in algebra will realize that a simple algorithm exists based on the Laplace expansion of the determinant of a permutation matrix. However, while rather similar to the algorithm above that counts inversions, it turned out to be a bit more complicated to program:

define lpsign(p[],n) {
auto s,q,r,j,k
scale=0
#
# Laplace expansion of determinant of permutation 
# matrix with a 1 in in row p[j] of column j
#
s=1
for (j=1;j < n;++j) {
q=p[j]
# apply checkerboard sign 
if (q%2 == 0) s=(-1)*s
for (k=j+1;k < n;++k) {
r=p[k]
# adjust numbers of remaining rows beyond row p[j]
# to account for having deleted row p[j]
if (r > q) p[k]=r-1
}
}
return(s)
}
So, based on simplicity, counting inversions appears to have the edge over all the other algorithms discussed above. However, based on speed, efficiently returning elements to their homes, and counting orbits both seem to be quite fast.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re(2): What I would NOT advocateRichard2006-08-07 16:31:55
Some Thoughtsre: What I would NOT advocateOld Original Oskar!2006-08-07 15:43:59
re(3): No SubjectRichard2006-08-07 14:14:05
re(2): No SubjectCharlie2006-08-07 13:10:13
re: No SubjectRichard2006-08-07 12:57:18
No SubjectAnd Or2006-08-07 10:46:16
What I would NOT advocateRichard2006-08-05 23:05:50
SolutionSimpleFederico Kereki2006-08-05 19:09:26
Solutionre: SolutionCharlie2006-08-05 17:24:50
SolutionSolutionBractals2006-08-05 16:14:10
SolutionTrivially?Old Original Oskar!2006-08-05 15:54:15
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 (1)
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