[r-t] Self-inverse changes
holroyd at math.ubc.ca
Tue May 19 07:50:38 UTC 2015
On Sun, 17 May 2015, Don Morrison wrote:
> 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.
> 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?
That's correct, and also correctly expressed. A self-inverse permutation
is also called an involution. I'm not sure in what sense you are claiming
this description is "slightly better" however.
> 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
That's correct, although the "p[i]!=i and" part is not necessary. If
p[i]=i then also p[p[i]]=i. If you remove the unnecessary condition then
you are precisely checking whether p^2 is the identity (as you said in the
first paragraph). More generally, to compose two permutations p,q you
compute p[q],...,p[q[N-1]] (by definition).
> 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?
That's true, but most programmers I know would consider this an
"optimization" only in a pretty obscure sense. From my (admittedly not
wide, but also not shallow) programming experience, the benefits of
transparent and straightforward code are likely to outweight those of a
(possible) (N-1)/N speed-up.
Similarly, unless you are sure this function is likely to be speed
critical, the (average) factor of 2 improvement from the short-circuit
loop termination might not be worth the extra obfuscation.
More information about the ringing-theory