[r-t] Self-inverse changes

[Don Morrison]

While an obvious algorithm for determining whether or not a change is
self-inverse is to simply apply it twice, or to simply compute its
inverse and compare, I believe slightly better can be done. In
particular, I think a self-inverse (finite) permutation must decompose
into disjoint 1-cycles and 2-cycles exclusively (presumably there is a
way to say this in group-theory-speak). Is this correct?

And, more to the point, am I correct in thinking that the following works?

Consider a (possibly jump) change at stage N to be a vector of N
positions, p[i], where i ranges from 0 to N-1, and where the p[i]s
range from 0 to N-1 with no duplicates.

A predicate for determining whether or not the change represented by p
is self-inverse is

For i from 0 to N-1:
  if p[i] != i and p[p[i]] != i
    return false
otherwise, if the loop terminates, return true

As a slight optimisation, I believe the upper bound on that loop can
be reduced from N-1 to N-2, since if all the first N-1 bells/places
are suitably arranged, the last must be, too. Is that true, or am I
missing something?



-- 
Don Morrison <dfm at ringing.org>
"The past is but a course prophesy of the future."
      -- Nathaniel Hawthorn, _The House of the Seven Gables_