A cross-bifix-free set of words is a set in which no prefix of any length of any word is the suffix of any other word in the set. A construction of cross-bifix-free sets has recently been proposed in Cheeet al.(2013) within a constant factor of optimality. We propose a Gray code for these cross-bifix-free sets and a CAT algorithm generating it. Our Gray code list is trace partitioned, that is, words with zero in the same positions are consecutive in the list.

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 functions 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 Gray code, we give efficient exhaustive generating algorithms and compare the obtained results.

In 1985, Simion and Schmidt gave a constructive bijection φ from the set of all length (n − 1) binary strings having no two consecutive 1s to the set of all length n permutations avoiding all patterns in {123,132,213}. In this paper, we generalize φ to an injective function from {0,1}n−1 to the set Sn of all length n permutations and derive from it four bijections φ : P →Q where P⊆{0,1}n−1 and Q ⊂ Sn. The domains are sets of restricted binary strings and the codomains are sets of pattern-avoiding permutations. As a particular case we retrieve the original Simion–Schmidt bijection. We also show that the bijections obtained are actually combinatorial isomorphisms, i.e. closeness-preserving bijections. Three of them have known Gray codes and generating algorithms for their domains and we present similar results for each corresponding codomain, under the appropriate combinatorial isomorphism.