Gray Codes for Involutions

Abstract

A Gray code is a list of words such that each word differs from its successor by a number of letters which is bounded independently of the length of the word. We use Roelants van Baronaigien’s I-code for involutions to derive a Gray code for all length-$n$ involutions and one for those with a given number of length-2 cycles. In both Gray codes, each involution is transformed into its successor via one or two transpositions or a rotation of three elements. For both Gray codes we obtain algorithms for passing between a word and its position in the list and a non-recursive sequencing algorithm (transforming a given word into its successor or determining that it is the last word in the list) which runs in $O(n)$ worst-case time and uses $O(1)$ auxiliary variables; for involutions with a given number of length-2 cycles we also obtain a sequencing algorithm which runs in $O(1)$ worst-case time and uses $O(n)$ auxiliary variables. We generalize Chase’s method for obtaining non-recursive sequencing algorithms to any list of words in which all the words with a given suffix form an interval of consecutive words, and we show that if in addition the letter preceding the suffix always takes at least two distinct values in that interval, then Ehrlich’s method will find in $O(1)$ time the rightmost letter in which a word differs from its successor.