Necklaces and Lyndon words in colexicographic order
2026-07-06 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors developed new algorithms that can list all 'necklaces' and 'Lyndon words'—special types of strings—of a given length using an alphabet with any number of letters. They introduced a new concept called 'quasinecklaces', which are easier to create and include all necklaces, making the process faster. They found a formula relating the number of quasinecklaces to necklaces, which helps their method run in constant amortized time. Their work also helps generate some special sequences like de Bruijn sequences under certain constraints.
necklaceLyndon wordcolexicographic orderquasinecklaceconstant amortized timede Bruijn sequencestring generationcombinatorics on wordsweight constraint
Authors
Daniel Gabric, Joe Sawada
Abstract
We present the first constant-amortized-time algorithms for generating all length-$n$ necklaces and Lyndon words over a $k$-letter alphabet in colexicographic order, for arbitrary $k\geq 2$. Our approach introduces a novel class of words called \emph{quasinecklaces}, which serve as an easily generated superset of necklaces through which all necklaces can be efficiently identified. We derive a formula for the number $Q_k(n)$ of length-$n$ quasinecklaces and show that $Q_k(n)$ is proportional to the number of length-$n$ necklaces, which is the key property needed to achieve constant amortized time. We also apply our results to efficiently generate a well-known de Bruijn sequence and efficiently generate necklaces and Lyndon words subject to a weight constraint.