Binary bubble languages and cool-lex order

DOI10.1016/J.JCTA.2011.07.005zbMath1314.68205OpenAlexW1997415583MaRDI QIDQ645969

Joe Sawada, Aaron Williams, Frank Ruskey

Publication date: 11 November 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcta.2011.07.005

zbMATH Keywords

algorithmsknapsack probleminterval graphsordered treesLyndon wordsexhaustive generationnecklacesconstant amortized timeGray codesDyck words

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Other designs, configurations (05B30) Boolean programming (90C09) Cyclic codes (94B15)

Related Items (20)

A universal cycle for strings with fixed-content (which are also known as multiset permutations) ⋮ Inside the binary reflected gray code: flip-swap languages in 2-gray code order ⋮ Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles ⋮ A shift Gray code for fixed-content Łukasiewicz words ⋮ A Gray code for fixed-density necklaces and Lyndon words in constant amortized time ⋮ Cool-lex order and \(k\)-ary Catalan structures ⋮ Flip-swap languages in binary reflected Gray code order ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ Properties of the cycles that contain all vectors of weight \(\le k\) ⋮ Constructing the first (and coolest) fixed-content universal cycle ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ Combinatorial Generation via Permutation Languages. V. Acyclic Orientations ⋮ The coolest way to generate binary strings ⋮ Traversing combinatorial 0/1-polytopes via optimization ⋮ Generating a Gray code for prefix normal words in amortized polylogarithmic time per word ⋮ De Bruijn Sequences for the Binary Strings with Maximum Density ⋮ On infinite prefix normal words ⋮ Bubble-flip -- a new generation algorithm for prefix normal words ⋮ Generating 2-Gray codes for ballot sequences in constant amortized time ⋮ Combinatorial generation via permutation languages. I. Fundamentals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Gray code for fixed-density necklaces and Lyndon words in constant amortized time
• Efficient oracles for generating binary bubble languages
• Loopless generation of linear extensions of a poset
• Gray codes for reflectable languages
• de Bruijn sequences and de Bruijn graphs for a general language
• The coolest way to generate combinations
• Universal cycles for combinatorial structures
• Gray codes from antimatroids
• Gray codes for necklaces
• A loopless algorithm for generating the permutations of a multiset
• Exhaustive generation of combinatorial objects by ECO
• A loop-free algorithm for generating the linear extensions of a poset
• Generating linear extensions of posets by transpositions
• On universal cycles of labeled graphs
• De Bruijn Sequences for Fixed-Weight Binary Strings
• De Bruijn Sequences for the Binary Strings with Maximum Density
• Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order
• Random Generation and Enumeration of Proper Interval Graphs
• Universal Cycles of Discrete Functions
• Generating Linear Extensions Fast
• Generating Multiset Permutations in Constant Time
• A Survey of Combinatorial Gray Codes
• A Gray Code for Necklaces of Fixed Density
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• Computing and Combinatorics

This page was built for publication: Binary bubble languages and cool-lex order