A Gray code for fixed-density necklaces and Lyndon words in constant amortized time

DOI10.1016/j.tcs.2012.01.013zbMath1296.68120OpenAlexW2040262311MaRDI QIDQ391391

Mohammad Hasan, H. S. Yoon

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.013

zbMATH Keywords

Gray codecool-lex orderfixed-density de Bruijn sequencefixed-density necklaceLyndon wordpseudo-necklace

Mathematics Subject Classification ID

Combinatorics on words (68R15) Combinatorial codes (94B25)

Related Items (15)

Finding the largest fixed-density necklace and Lyndon word ⋮ Inside the binary reflected gray code: flip-swap languages in 2-gray code order ⋮ Necklaces and Lyndon words in colexicographic and binary reflected Gray code order ⋮ Polytopes associated with symmetry handling ⋮ 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 ⋮ Constructing the first (and coolest) fixed-content universal cycle ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ Binary bubble languages and cool-lex order ⋮ The coolest way to generate binary strings ⋮ Ranking and unranking fixed-density necklaces and Lyndon words ⋮ A Legendre pair of length 77 using complementary binary matrices with fixed marginals ⋮ De Bruijn Sequences for the Binary Strings with Maximum Density ⋮ Counting the decimation classes of binary vectors with relatively prime length and density

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient oracles for generating binary bubble languages
• Binary bubble languages and cool-lex order
• Symmetry types of periodic sequences
• Gray-ordered binary necklaces
• More restrictive Gray codes for necklaces and Lyndon words
• An algorithm for generating necklaces of beads in two colors
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Gray codes for necklaces
• De Bruijn Sequences for Fixed-Weight Binary Strings
• Factorizing words over an ordered alphabet
• Generating necklaces
• A Gray Code for Necklaces of Fixed Density
• An Efficient Algorithm for Generating Necklaces with Fixed Density

This page was built for publication: A Gray code for fixed-density necklaces and Lyndon words in constant amortized time