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. |