Greedy Gray Codes for Dyck Words and Ballot Sequences

We present a simple greedy algorithm for generating Gray codes for Dyck words and fixed-weight Dyck prefixes. Successive strings in our listings differ from each other by a transposition, that is, two bit changes. Our Gray codes are both homogeneous and suffix partitioned. Furthermore, we use our greedy algorithm to produce the first known homogeneous 2-Gray code for ballot sequences, which are Dyck prefixes of all weights. Our work extends a previous result on combinations by Williams [Conference proceedings: Workshop on Algorithms and Data Structures (WADS), LNTCS 8037:525-536, 2013].