Binary bubble languages and cool-lex order

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:119

Article

Ruskey, Frank¹  Sawada, Joe²  Williams, Aaron³ 

[1] Univ Victoria, Dept Comp Sci, Victoria, BC V8W 3N4, Canada

[2] Univ Guelph, Sch Comp Sci, Guelph, ON N1G 2W1, Canada

[3] Carleton Univ, Sch Math & Stat, Ottawa, ON K1S 5B6, Canada

关键词: Exhaustive generation;    Gray codes;    Algorithms;    Constant amortized time;    Necklaces;    Lyndon words;    Ordered trees;    Dyck words;    Interval graphs;    Knapsack problem;   

DOI  :  10.1016/j.jcta.2011.07.005

来源: Elsevier

【 摘 要 】

A bubble language is a set of binary strings with a simple closure property: The first 01 Of any string can be replaced by 10 to obtain another string in the set.. Natural representations of many combinatorial objects are bubble languages. Examples include binary string representations of k-ary trees, unit interval graphs, linear-extensions of B-posets, binary necklaces and Lyndon words, and feasible solutions to knapsack problems. In co-lexicographic order, fixed-weight binary strings are ordered so that their suffixes of the form 10(i) occur (recursively) in the order i = max, max - 1, ... , min + 1, min for some values of max and min. In cool-lex order the suffixes occur (recursively) in the order max - 1, ... , min + 1, min. max. This small change has significant consequences. We prove that the strings in any bubble language appear in a Gray code order when listed in cool-lex order. This Gray code may be viewed from two different perspectives. On one hand, successive binary strings differ by one or two transpositions, and on the other hand, they differ by a shift of some substring one position to the right. This article also provides the theoretical foundation for many efficient generation algorithms, as well as the first construction of fixed-weight binary de Bruijn sequences; results that will appear in subsequent articles. (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free