Generating 2-Gray codes for ballot sequences in constant amortized time

Dennis Wong; Fabio Calero; Kushal Sedhai

doi:10.1016/j.disc.2022.113168

Generating 2-Gray codes for ballot sequences in constant amortized time

Dennis Wong, Fabio Calero, Kushal Sedhai

Faculty of Applied Sciences

Stony Brook University

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

We present a simple algorithm that generates a cyclic 2-Gray code for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known cyclic 2-Gray code for ballot sequences that achieves this time bound. In addition, the algorithm can be easily modified to output ballot sequences in binary reflected Gray code order in constant amortized time per string using a linear amount of space.

Original language	English
Article number	113168
Journal	Discrete Mathematics
Volume	346
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2022.113168
Publication status	Published - Jan 2023

Keywords

Ballot sequence
Binary reflected Gray code
CAT algorithm
Dyck words
Flip-swap language
Gray code

Access to Document

10.1016/j.disc.2022.113168

Cite this

@article{5b1aa120fbd54eeda32410fc969fe761,

title = "Generating 2-Gray codes for ballot sequences in constant amortized time",

abstract = "We present a simple algorithm that generates a cyclic 2-Gray code for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known cyclic 2-Gray code for ballot sequences that achieves this time bound. In addition, the algorithm can be easily modified to output ballot sequences in binary reflected Gray code order in constant amortized time per string using a linear amount of space.",

keywords = "Ballot sequence, Binary reflected Gray code, CAT algorithm, Dyck words, Flip-swap language, Gray code",

author = "Dennis Wong and Fabio Calero and Kushal Sedhai",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2023",

month = jan,

doi = "10.1016/j.disc.2022.113168",

language = "English",

volume = "346",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Generating 2-Gray codes for ballot sequences in constant amortized time

AU - Wong, Dennis

AU - Calero, Fabio

AU - Sedhai, Kushal

PY - 2023/1

Y1 - 2023/1

N2 - We present a simple algorithm that generates a cyclic 2-Gray code for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known cyclic 2-Gray code for ballot sequences that achieves this time bound. In addition, the algorithm can be easily modified to output ballot sequences in binary reflected Gray code order in constant amortized time per string using a linear amount of space.

AB - We present a simple algorithm that generates a cyclic 2-Gray code for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known cyclic 2-Gray code for ballot sequences that achieves this time bound. In addition, the algorithm can be easily modified to output ballot sequences in binary reflected Gray code order in constant amortized time per string using a linear amount of space.

KW - Ballot sequence

KW - Binary reflected Gray code

KW - CAT algorithm

KW - Dyck words

KW - Flip-swap language

KW - Gray code

UR - http://www.scopus.com/inward/record.url?scp=85138129576&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2022.113168

DO - 10.1016/j.disc.2022.113168

M3 - Article

AN - SCOPUS:85138129576

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

M1 - 113168

ER -

Generating 2-Gray codes for ballot sequences in constant amortized time

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this