On the exhaustive generation of generalized ballot sequences in lexicographic and Gray code order
Ahmad Sabri, Vincent Vajnovszki · Pure mathematics and applications · 2019
Abstract A generalized (resp. p -ary) ballot sequence is a sequence over the set of non-negative integers (resp. integers less than p ) where in any of its prefixes each positive integer i occurs at most as often as any integer less than i . We show that the Reected Gray Code order induces a cyclic 3-adjacent Gray code on both, the set of fixed length generalized ballot sequences and p -ary ballot sequences when p is even, that is, ordered list where consecutive sequences (regarding the list cyclically) differ in at most 3 adjacent positions. Non-trivial efficient generating algorithms for these ballot sequences, in lexicographic order and for the obtained Gray codes, are also presented.