Generating 2-Gray codes for ballot sequences in constant amortized time |
| |
Affiliation: | 1. Macao Polytechnic University, China;2. State University of New York, Korea, Republic of Korea |
| |
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 Gray code CAT algorithm Binary reflected Gray code Flip-swap language Dyck words |
本文献已被 ScienceDirect 等数据库收录! |