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

 Sign of a Permutation (Posted on 2006-08-05)
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.

 Subject Author Date re(2): What I would NOT advocate Richard 2006-08-07 16:31:55 re: What I would NOT advocate Old Original Oskar! 2006-08-07 15:43:59 re(3): No Subject Richard 2006-08-07 14:14:05 re(2): No Subject Charlie 2006-08-07 13:10:13 re: No Subject Richard 2006-08-07 12:57:18 No Subject And Or 2006-08-07 10:46:16 What I would NOT advocate Richard 2006-08-05 23:05:50 Simple Federico Kereki 2006-08-05 19:09:26 re: Solution Charlie 2006-08-05 17:24:50 Solution Bractals 2006-08-05 16:14:10 Trivially? Old Original Oskar! 2006-08-05 15:54:15

 Search: Search body:
Forums (0)