Efficient Oracles for Generating Binary Bubble Languages

J. Sawada, A. Williams

Abstract


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.

Full Text: PDF