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