Efficient oracles for generating binary bubble languages
The electronic journal of combinatorics, Tome 19 (2012) no. 1
A simple meta-algorithm is provided to efficiently generate a wide variety of combinatorial objects that can be represented by binary strings with a fixed number of 1s. Such objects include: $k$-ary Dyck words, connected unit interval graphs, binary strings lexicographically larger than $\omega$, those avoiding $10^k$ for fixed $k$, reversible strings and feasible solutions to knapsack problems. Each object requires only a very simple object-specific subroutine (oracle) that plugs into the generic cool-lex framework introduced by Williams. The result is that each object can be generated in amortized $O(1)$-time. Moreover, the strings can be listed in either a conventional co-lexicographic order, or in the cool-lex Gray code order.
DOI :
10.37236/2051
Classification :
68W32, 05A05, 68R05, 68W05
Mots-clés : bubble language, Gray code, cool-lex, unit interval graph, knapsack, reversible strings, CAT algorithm, necklace, Lyndon word
Mots-clés : bubble language, Gray code, cool-lex, unit interval graph, knapsack, reversible strings, CAT algorithm, necklace, Lyndon word
@article{10_37236_2051,
author = {J. Sawada and A. Williams},
title = {Efficient oracles for generating binary bubble languages},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {1},
doi = {10.37236/2051},
zbl = {1362.68304},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2051/}
}
J. Sawada; A. Williams. Efficient oracles for generating binary bubble languages. The electronic journal of combinatorics, Tome 19 (2012) no. 1. doi: 10.37236/2051
Cité par Sources :