Two Reflected Gray Code-Based Orders on Some Restricted Growth Sequences
Ahmad Sabri, Vincent Vajnovszki · The Computer Journal · 2014
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.