<abstract xmlns="http://www.w3.org/1999/xhtml"><p>A generalized (resp. <italic>p</italic>-ary) ballot sequence is a sequence over the set of non-negative integers (resp. integers less than <italic>p</italic>) where in any of its prefixes each positive integer <italic>i</italic> occurs at most as often as any integer less than <italic>i</italic>. 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 <italic>p</italic>-ary ballot sequences when <italic>p</italic> 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.</p></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.

On the exhaustive generation of generalized ballot sequences in lexicographic and Gray code order

LIB, Université Bourgogne Franche-Comté,

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

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...

On the exhaustive generation of generalized ballot sequences in lexicographic and Gray code order

Online veröffentlicht: 01. Nov. 2019

Seitenbereich: 109 - 119

Eingereicht: 07. Nov. 2018

DOI: https://doi.org/10.1515/puma-2015-0035

Schlüsselwörter
(reflected) Gray code, exhaustive generation, generalized ballot sequence

© 2019 Ahmad Sabri et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

On the exhaustive generation of generalized ballot sequences in lexicographic and Gray code order

Online veröffentlicht: 01. Nov. 2019

Seitenbereich: 109 - 119

Eingereicht: 07. Nov. 2018

DOI: https://doi.org/10.1515/puma-2015-0035

Schlüsselwörter(reflected) Gray code, exhaustive generation, generalized ballot sequence

© 2019 Ahmad Sabri et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Schlüsselwörter
(reflected) Gray code, exhaustive generation, generalized ballot sequence