Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences

DOI10.1016/J.JDA.2017.01.003zbMATH Open1370.68343OpenAlexW2586556622MaRDI QIDQ2397155FDOQ2397155

Authors: Joe Sawada, Aaron Williams 

Publication date: 29 May 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2017.01.003

Recommendations

• Ranking and unranking fixed-density necklaces and Lyndon words
• Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence
• Necklaces and Lyndon words in colexicographic and binary reflected Gray code order
• Computing \(k\)-th Lyndon word and decoding lexicographically minimal de Bruijn sequence
• Publication:4952625

zbMATH Keywords

de Bruijn sequenceLyndon wordnecklacerankingunranking

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Cites Work

• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Computing \(k\)-th Lyndon word and decoding lexicographically minimal de Bruijn sequence
• Factorizing words over an ordered alphabet
• Title not available (Why is that?)
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• Enumerating, Ranking and Unranking Binary Trees
• A Unified Setting for Selection Algorithms (II)
• Title not available (Why is that?)
• Lexicographically least circular substrings
• Generating necklaces
• Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
• Lexicographic compositions and de Bruijn sequences
• Ranking and unranking permutations in linear time
• Ranking and unranking of B-trees
• Ranking and Listing Algorithms for k-Ary Trees
• Title not available (Why is that?)
• Ranking and Unranking of 2-3 Trees
• Ranking Algorithms for Lists of Partitions
• Title not available (Why is that?)
• Ranking and Unranking of AVL-Trees
• Generating bracelets in constant amortized time
• Efficient indexing of necklaces and irreducible polynomials over finite fields
• The standard factorization of Lyndon words: an average point of view
• Title not available (Why is that?)

Cited In (9)

• Computing \(k\)-th Lyndon word and decoding lexicographically minimal de Bruijn sequence
• Ranking binary unlabelled necklaces in polynomial time
• Ranking and Unranking k-Subsequence Universal Words
• Efficient reconfiguration algorithms of de Bruijn and Kautz networks into linear arrays
• Necklaces and Lyndon words in colexicographic and binary reflected Gray code order
• Ranking and unranking fixed-density necklaces and Lyndon words
• Finding the largest fixed-density necklace and Lyndon word
• Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence
• Ranking and unranking bordered and unbordered words

This page was built for publication: Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397155)