Efficient oracles for generating binary bubble languages
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.
- Cool-lex order and k-ary Catalan structures
- Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
- A Gray code for fixed-density necklaces and Lyndon words in constant amortized time
- The coolest way to generate binary strings
- Combinatorial generation via permutation languages. I: Fundamentals
- On infinite prefix normal words
- Bubble-flip -- a new generation algorithm for prefix normal words
- Binary bubble languages and cool-lex order
- Traversing combinatorial 0/1-polytopes via optimization
- Successor rules for flipping pancakes and burnt pancakes
This page was built for publication: Efficient oracles for generating binary bubble languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426808)
