[r-t] Self-inverse changes

[Alexander Holroyd]

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.

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?

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[0]],...,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.

cheers, Ander