0000000000121232
AUTHOR
Ahmad Sabri
Gray codes and efficient exhaustive generation for several classes of restricted words
We consider Gray codes and efficient exhaustive generating algorithms for the sets belonging to three major classes of restricted words, that are: (1) restricted growth sequences, (2) factor avoiding q-ary words, and (3) pattern avoiding permutations. For the first two classes, our Gray codes (and thus, our generating algorithms) are based on order relations obtained by specializing known order relations; namely Reflected Gray Code (RGC) order and its variations, and we call them Reflected Gray Code based orders. The Gray code and the generating algorithm for the third class are based on Steinhaus-Johnson-Trotter order, that is, order relation induced by Steinhaus-Johnson-Trotter Gray code …
Two Reflected Gray Code-Based Orders on Some Restricted Growth Sequences
We consider two order relations: that induced by the m-ary reflected Gray code and a suffix partitioned variation of it. We show that both of them when applied to some sets of restricted growth sequences still yield Gray codes. These sets of sequences are: subexcedant and ascent sequences, restricted growth functions and staircase words. In particular, we give the first suffix partitioned Gray codes for restricted growth f unctions and ascent sequences; these latter sequences code various combinatorial classes as interval orders, upper triangular matrices without zero rows and zero columns whose non-negative integer entries sum up to n, and certain pattern-avoiding permutations. For each Gr…