Generating necklaces

DOI10.1016/0196-6774(92)90047-GzbMath0764.68104MaRDI QIDQ4020354

Carla D. Savage, Terry Min Yih Wang, Frank Ruskey

Publication date: 16 January 1993

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

Full work available at URL: https://doi.org/10.1016/0196-6774(92)90047-g

zbMATH Keywords

FKM algorithm; necklace

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

Related Items

SYMMETRIC ITINERARY SETS: ALGORITHMS AND NONLINEAR EXAMPLES, Completely uniformly distributed sequences based on de Bruijn sequences, Unnamed Item, On infinite prefix normal words, Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions, The k-centre problem for classes of cyclic words, A Gray code for fixed-density necklaces and Lyndon words in constant amortized time, The lexicographically smallest universal cycle for binary strings with minimum specified weight, The coolest way to generate binary strings, On prefix normal words and prefix normal forms, Constructing new covering arrays from LFSR sequences over finite fields, More restrictive Gray codes for necklaces and Lyndon words, de Bruijn sequences and de Bruijn graphs for a general language, Minimum Eulerian circuits and minimum de Bruijn sequences, Average cost of Duval's algorithm for generating Lyndon words, An efficient shift rule for the prefer-max de Bruijn sequence, Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence, Constructing de Bruijn sequences by concatenating smaller universal cycles, Necklaces and Lyndon words in colexicographic and binary reflected Gray code order, \(k\)-ary Lyndon words and necklaces arising as rational arguments of Hurwitz-Lerch zeta function and Apostol-Bernoulli polynomials, Enumerating words with forbidden factors, Gray cycles of maximum length related to \(k\)-character substitutions, A characterization of binary morphisms generating Lyndon infinite words, An efficient generalized shift-rule for the prefer-max de Bruijn sequence, Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences, Generalized de Bruijn words for primitive words and powers, Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles, Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence, Generating fixed density bracelets of arbitrary base, De Bruijn Sequences for the Binary Strings with Maximum Density