Necklaces and Lyndon words in colexicographic order

Q: What problem does the paper address for necklaces and Lyndon words?

The paper targets efficient generation of all length-n necklaces and Lyndon words over a k-letter alphabet specifically in colexicographic order, achieving constant amortized time for any k≥2.

Q: What are quasinecklaces and why are they introduced?

Quasinecklaces form a novel word class that serves as an easily generated superset of necklaces, allowing all necklaces to be efficiently identified during generation.

Q: How does the paper ensure constant amortized time?

It derives a formula and bound for the number Qk(n) of length-n quasinecklaces and shows Qk(n) is proportional to the number of length-n necklaces, which is the key property used to obtain constant amortized time.

Jul 16, 2026

Upload by Ezra

Constant-amortized-time algorithms generate all length-n necklaces and Lyndon words over a k-letter ordered alphabet in colexicographic order for any k≥2. The work introduces quasinecklaces as an efficiently generated superset that enables identifying all necklaces. A counting formula for the number Qk(n) of length-n quasinecklaces shows Qk(n) is proportional to the number of length-n necklaces, providing the key bound for constant amortized time. Applications include efficient generation of the Grandmama de Bruijn sequence and necklaces/Lyndon words under a weight constraint.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages21

Reading Time53 min

Introduction

Main results

Outline

Preliminaries

Notation and definitions

Quasinecklaces and CAT generation

Counting Qk(n)

Generating necklaces and Lyndon words in colex order

Running time and weight constraint

Applications

de Bruijn sequence and universal cycles

arXiv :2607 .05324v1 [math .CO] 6 Jul 2026 Necklaces and Lyndon words in colexicographic order Daniel Gabri´c and Joe Sawada School of Computer Science University of Guelph 50 Stone Road East Guelph, ON N1G 2W1 Canada [dgabric@uoguelph. ca](dgabric@uoguelph. ca) [jsawada@uoguelph. ca](jsawada@uoguelph. ca) 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 ≥ 2. Our approach introduces a novel class of words called 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. Keywords—Necklace, Lyndon word, colex order, Grandmama de Bruijn sequence, quasinecklace 1 Introduction Let Σk denote the k-letter totally ordered alphabet {1 , 2 ,..., k} where 1 < 2 < ··· < k. Throughout this paper, we implicitly assume all words have symbols from Σk . We call a word w a necklace 1 if it is, not necessarily uniquely, lexicographically smallest among all of its nontrivial rotations. The word w is a Lyndon word if it is strictly smaller than all of its nontrivial rotations. For example, the word 113213 is both a necklace and a Lyndon word, 121212 is a necklace but not a Lyndon word, and the word 12312 is neither a Lyndon word nor a necklace. Necklaces and Lyndon words are classical objects in combinatorics on words 1 Necklaces are also commonly referred to as equivalence classes of words under rotation. and have many practical applications. For example, they appear in string algorithms [1 , 8], coding theory [12 , 13], bionformatics [3 , 15 , 17], and even music theory [6] . The study of necklaces and Lyndon words naturally raises the question of how to generate them efficiently. We call a generation algorithm constant amortized time (CAT) if the total work performed divided by the number of objects generated is bounded by a constant. Several CAT algorithms for generating necklaces and Lyndon words in lexicographic order are known. Fredricksen, Kessler, and Maiorana [10 , 11] presented the FKM algorithm, which generates necklaces in lexicographic order and was subsequently shown to be CAT by Ruskey et al. [18] . Duval [9] independently discovered a different lexicographic algorithm for necklaces, later proved to run in CAT by Berstel and Pocchiola [2] . Notably, the lexicographically least rotation of a de Bruijn sequence can be obtained by concatenating the Lyndon words generated by Duval’s algorithm. Although necklaces and Lyndon words can already be efficiently generated in lexicographic order, some applications rely on different orderings. For example, the Grandmamade Bruijn sequence [7] is constructed by concatenating the primitive roots of all necklaces arranged in colexicographic (colex) order, and colex orderings of necklaces also arise in the construction of universal cycles for subsets [4] . Sawada et al. [19 , 20] introduced a CAT algorithm to generate binary necklaces in colex order. Their method relies on an auxiliary set of words called pseudonecklaces, which are easy to generate in colex order and whose cardinality is proportional to that of binary necklaces. For alphabets of size k ≥ 3, however, no such CAT generation algorithm has been available. Main results. In this paper, we resolve this gap by presenting the first CAT algorithms for generating k-ary necklaces and Lyndon words in colex order for arbitrary k ≥ 2. To do so, we introduce a novel class of words called quasinecklaces. Quasinecklaces are similar in

FAQs

What problem does the paper address for necklaces and Lyndon words?

The paper targets efficient generation of all length-n necklaces and Lyndon words over a k-letter alphabet specifically in colexicographic order, achieving constant amortized time for any k≥2.

What are quasinecklaces and why are they introduced?

Quasinecklaces form a novel word class that serves as an easily generated superset of necklaces, allowing all necklaces to be efficiently identified during generation.

How does the paper ensure constant amortized time?

It derives a formula and bound for the number Qk(n) of length-n quasinecklaces and shows Qk(n) is proportional to the number of length-n necklaces, which is the key property used to obtain constant amortized time.

Jul 16, 2026

Upload by Ezra