[r-t] Self-inverse changes
Don Morrison
dfm at ringing.org
Sun May 17 18:31:24 UTC 2015
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_
More information about the ringing-theory
mailing list