{"id":"arxiv/2607.05324","url":"https://arxiv.org/abs/2607.05324","tags":["math.CO","cs.DS"],"score":0,"title":"Necklaces and Lyndon words in colexicographic order","domain":"math.CO","source":"arxiv","authors":["Daniel Gabric","Joe Sawada"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-06","reactions":{}}