6533b7d0fe1ef96bd125ab50

RESEARCH PRODUCT

Gray codes and efficient exhaustive generation for several classes of restricted words

subject

description

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 for permutations. In the first results, we define Gray codes and give efficient generating algorithms for the class of restricted growth sequences that satisfy our prescribed properties. In particular, we focus on four mainstream subclasses: subexcedant and ascent sequences, restricted growth functions and staircase words. The results are given in two parts: by using original RGC order and Co-RGC order, which generates prefix (and suffix, respectively) partitioned Gray codes; and we give comparison between the two results. In addition, we investigate the Graycodeness of the restricted ascent sequences.In the second results, we define Gray codes and give an efficient generating algorithm for the class of factor avoiding q-ary words. Among the involved tools, we make use of original RGC order for even q and Dual RGC order for odd q, the zero periodicity property, and word matching techniques adapted from that of Knuth-Morris-Pratt. We give the implementation of these results to define Gray code and generating algorithm for cross-bifix-free sets.In the third results, we define Gray codes and give efficient generating algorithms for the class of pattern avoiding permutations. In particular, we show that the Steinhaus-Johnson-Trotter Gray code for permutations, when restricted by avoiding some set of patterns, still remains a (possibly less restricted) Gray code. The main ingredients we are using in the investigation of the Graycodeness are: succession functions, the classical bijection from inversion tables to permutations, and the list of inversion tables with respect to RGC order. We give additional results on graph theoretic consequences.