Efficient oracles for generating binary bubble languages (Q426808)

Summary: 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 1's. 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.