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

DOI10.1016/J.JDA.2017.01.003MaRDI QIDQ2397155zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

de Bruijn sequenceLyndon wordnecklacerankingunranking

Mathematics Subject Classification ID

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

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

Cites work

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

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)