Abstract
dc:description.abstractCombinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding to the balanced parentheses (()()). Given a string s = s1 s2 sn, the right-shift operation shift(s, i, j) replaces the substring si si+1..sj by si+1..sj si. In other words, si is right-shifted into position j by applying the permutation (j j−1 .. i) to the indices of s. Right-shifts include prefix-shifts (i = 1) and adjacent-transpositions (j = i+1). A fixed-content language is a set of strings that contain the same multiset of symbols. Given a fixed-content language, a shift Gray code is a list of its strings where consecutive strings differ by a shift. This thesis asks if shift Gray codes exist for a variety of combinatorial objects. This abstract question leads to a number of practical answers. The first prefix-shift Gray code for multiset permutations is discovered, and it provides the first algorithm for generating multiset permutations in O(1)-time while using O(1) additional variables. Applications of these results include more efficient exhaustive solutions to stacker-crane problems, which are natural NP-complete traveling salesman variants. This thesis also produces the fastest algorithm for generating balanced parentheses in an array, and the first minimal-change order for fixed-content necklaces and Lyndon words. These results are consequences of the following theorem: Every bubble language has a right-shift Gray code. Bubble languages are fixed-content languages that are closed under certain adjacent-transpositions. These languages generalize classic combinatorial objects: k-ary trees, ordered trees with fixed branching sequences, unit interval graphs, restricted Schr oder and Motzkin paths, linear-extensions of B-posets, and their unions, intersections, and quotients. Each Gray code is circular and is obtained from a new variation of lexicographic order known as cool-lex order. Gray codes using only shift(s, 1, n) and shift(s, 1, n−1) are also found for multiset permutations. A universal cycle that omits the last (redundant) symbol from each permutation is obtained by recording the first symbol of each permutation in this Gray code. As a special case, these shorthand universal cycles provide a new fixed-density analogue to de Bruijn cycles, and the first universal cycle for the "middle levels" (binary strings of length 2k + 1 with sum k or k + 1).
Degree
thesis:*- Level thesis:degree_level
- Doctor of Philosophy Ph.D.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Williams, Aaron Michael
- Advisors dc:contributor.supervisor
-
- Ruskey, Frank
- Myrvold, W. J.
Subjects
dc:subject × 37- shorthand universal cycles
- combinatorial generation
- minimal-change order
- loopless algorithm
- efficient algorithm
- combinations
- multiset permutations
- balanced parentheses
- Dyck words
- Catalan paths
- Schroder paths
- Motzkin words
- linear-extensions
- posets
- connected unit interval graphs
- inversions
- binary trees
- k-ary trees
- ordered trees with fixed branching sequence
- Lyndon words
- pre-necklaces
- theoretical computer science
- discrete mathematics
- combinatorics
- brute forcs
- de Bruijn cycles
- bubble languages
- cool-lex order
- lexicographic order
- combinatorial enumeration
- stacker-crane problem
- traveling salesman problem
- middle levels
- fixed-density de Bruijn cycle
- fixed-content
- UVic Subject Index::Sciences and Engineering::Applied Sciences::Computer science
- UVic Subject Index::Sciences and Engineering::Mathematics
Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Dc Identifier Citation
-
A. Williams. Loopless generation of multiset permutations using a constant number of variables by pre x shifts. In SODA '09: The Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, New York, USA, 2009.
F. Ruskey and A. Williams. The coolest way to generate combinations. Discrete Mathematics, 309(17):5305{5320, September 2009.
F. Ruskey and A. Williams. Generating balanced parentheses and binary trees by pre x shifts. In CATS '08: Fourteenth Computing: The Australasian Theory Symposium, volume 77 of CRPIT, Wollongong, Australia, 2008. ACS.
F. Ruskey and A. Williams. An explicit universal cycle for the (n − 1)- permutations of an n-set. ACM Transactions on Algorithms, (accepted), 2008.
F. Ruskey and A. Williams. Generating combinations by pre x shifts. In COCOON '05: Computing and Combinatorics, 11th Annual International Conference, volume 3595 of Lecture Notes in Computer Science, pages 570{576, Kunming, China, 2005. Springer-Verlag.