Generating necklaces

DOI10.1016/0196-6774(92)90047-GzbMath0764.68104OpenAlexW2913978532MaRDI 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 algorithmnecklace

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items (30)

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

This page was built for publication: Generating necklaces