Combinatorics on words in pure Python with zero dependencies: Lyndon-word testing, Duval's Chen-Fox-Lyndon factorization, necklace and bracelet enumeration, and De Bruijn sequences.
A Lyndon word is a non-empty word that is strictly smaller than all of its rotations. Lyndon words are the building blocks of combinatorics on words: every word factors uniquely into a non-increasing concatenation of Lyndon words (the Chen-Fox-Lyndon theorem), and Lyndon words index the necklaces (rotation classes) and the De Bruijn sequences over an alphabet.
This library implements the classic algorithms directly, with no dependencies and strict typing.
pip install lyndon-words
from lyndon_words import is_lyndon, factorize, standard_factorization, enumerate_necklaces, enumerate_bracelets, de_bruijn, lyndon_array # Lyndon-word test (accepts str, list, or tuple) is_lyndon("aab") # True is_lyndon("aba") # False is_lyndon((0, 0, 1)) # True # Duval's Chen-Fox-Lyndon factorization (non-increasing Lyndon factors) factorize("banana") # ['b', 'an', 'an', 'a'] factorize("aababab") # ['aabab', 'ab'] # Standard factorization of a Lyndon word: (u, v) with v the longest proper # Lyndon suffix; both parts are Lyndon and u < v standard_factorization("aab") # ('a', 'ab') standard_factorization("abb") # ('ab', 'b') standard_factorization("aabac") # ('a', 'abac') # Necklaces: rotation-class representatives over {0, 1} of length 3 list(enumerate_necklaces(alphabet_size=2, length=3)) # [(0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1)] # Bracelets: rotation + reflection classes over {0, 1} of length 4 list(enumerate_bracelets(alphabet_size=2, length=4)) # [(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 1), (1, 1, 1, 1)] # De Bruijn sequence B(2, 3): every length-3 binary word appears once cyclically de_bruijn(alphabet_size=2, length=3) # (0, 0, 0, 1, 0, 1, 1, 1) # Lyndon array: longest Lyndon prefix length at each position lyndon_array("banana") # [1, 2, 1, 2, 1, 1] lyndon_array("abcd") # [4, 3, 2, 1] (entire increasing suffix is Lyndon) lyndon_array("aaaa") # [1, 1, 1, 1] (all equal, no run > 1 is Lyndon) lyndon_array("0010011") # [7, 2, 1, 4, 3, 1, 1] # Closed-form counts (exact big-int arithmetic, no enumeration needed) from lyndon_words import necklace_count, lyndon_word_count, bracelet_count necklace_count(alphabet_size=2, length=4) # 6 (matches len(enumerate_necklaces(...))) lyndon_word_count(alphabet_size=2, length=4) # 3 (aperiodic necklaces) bracelet_count(alphabet_size=2, length=4) # 6 (matches len(enumerate_bracelets(...)))
Words over an integer alphabet are represented as tuple[int, ...], for example
(0, 0, 1) for a 3-symbol word over {0, 1}. This is the canonical type, and every
enumeration and generation function (enumerate_necklaces, enumerate_bracelets,
de_bruijn) yields or returns tuples of ints.
The word predicates is_lyndon and factorize are generic over any comparable
Sequence, so str, list, and tuple all work. The factors returned by factorize
have the same type as the input: pass a str and you get a list of str factors, pass a
tuple and you get a list of tuple factors. String examples like "aab" behave exactly
like integer tuples because string comparison is lexicographic.
Enumeration and generation functions take keyword-only alphabet_size and length.
| Function | Description |
|---|---|
is_lyndon(word) |
True iff word is non-empty and strictly smaller than all proper rotations |
factorize(word) |
Duval's O(n) Chen-Fox-Lyndon factorization into non-increasing Lyndon factors |
standard_factorization(word) |
Right standard factorization (u, v) of a Lyndon word: v is the longest proper Lyndon suffix; both parts are Lyndon and u < v |
lyndon_array(word) |
For each index i, the length of the longest Lyndon prefix of word[i:] |
enumerate_necklaces(*, alphabet_size, length) |
FKM enumeration of rotation classes, lexicographic order |
enumerate_bracelets(*, alphabet_size, length) |
Enumeration of rotation + reflection classes, lexicographic order |
de_bruijn(*, alphabet_size, length) |
De Bruijn sequence B(alphabet_size, length) via FKM |
necklace_count(*, alphabet_size, length) |
Number of necklaces via Moreau's totient sum, in closed form |
lyndon_word_count(*, alphabet_size, length) |
Number of Lyndon words (aperiodic necklaces) via Mobius inversion |
bracelet_count(*, alphabet_size, length) |
Number of bracelets via the Burnside sum over the dihedral group |
alphabet_size >= 1 and length >= 1 are required; otherwise a ValueError is raised.
Lyndon word. A non-empty word strictly smaller, in lexicographic order, than every one of its proper rotations (equivalently, every proper suffix). Lyndon words are aperiodic.
Chen-Fox-Lyndon factorization. Every non-empty word factors uniquely into Lyndon words
l_1 >= l_2 >= ... >= l_m. Duval's algorithm computes this in O(n) time and O(1) extra
space.
Standard factorization. For a Lyndon word w of length at least 2, the
(right) standard factorization is the unique pair (u, v) with w = u + v
where v is the longest proper suffix of w that is itself a Lyndon word. The
standard-factorization theorem guarantees that u is then also a Lyndon word
and that u < v. A single-letter Lyndon word has no standard factorization.
Necklace. A rotation-equivalence class of length-n words. The representative is the
lexicographically least rotation. necklace_count(alphabet_size=k, length=n) returns the
count in closed form via Moreau's necklace-counting function
N(k, n) = (1/n) * sum over d dividing n of phi(d) * k^(n/d), where phi is Euler's
totient. This equals len(list(enumerate_necklaces(alphabet_size=k, length=n))).
Lyndon-word count. A Lyndon word is an aperiodic necklace, so the number of Lyndon
words of length n is the Mobius inversion of the necklace identity:
L(k, n) = (1/n) * sum over d dividing n of mu(d) * k^(n/d), where mu is the Mobius
function. lyndon_word_count(alphabet_size=k, length=n) returns this, and the divisor
identity sum over d dividing n of d * L(k, d) = k^n holds.
Bracelet. An equivalence class under rotation and reflection (the dihedral group). The
representative is the lexicographically least element of the orbit.
bracelet_count(alphabet_size=k, length=n) returns the count via the Burnside
(orbit-counting) sum over the dihedral group: the rotations together fix
sum over d dividing n of phi(d) * k^(n/d) words, and the n reflections fix
n * k^((n+1)/2) words when n is odd, or (n/2) * (k^(n/2+1) + k^(n/2)) words when n
is even; the bracelet count is their total divided by 2n. This equals
len(list(enumerate_bracelets(alphabet_size=k, length=n))).
Lyndon array. For a word s of length n, the Lyndon array is the integer array
L where L[i] is the length of the longest Lyndon word that is a prefix of s[i:].
Every entry satisfies 1 <= L[i] <= n - i. The first entry L[0] equals the length of
the first (leftmost) factor in the Chen-Fox-Lyndon factorization of s: that factor is
the unique longest Lyndon prefix of the entire word.
De Bruijn sequence. A cyclic sequence B(k, n) of length k^n in which every
length-n word appears exactly once as a contiguous cyclic subword. The FKM construction
concatenates, in lexicographic order, every Lyndon word whose length divides n.
- Duval, J.-P. (1983). Factorizing words over an ordered alphabet. Journal of Algorithms.
- Chen, K.-T., Fox, R. H., Lyndon, R. C. (1958). Free differential calculus IV. Annals of Mathematics.
- Fredricksen, H., Maiorana, J. (1978). Necklaces of beads in k colors and k-ary de Bruijn sequences. Discrete Mathematics.
- Fredricksen, H., Kessler, I. J. (1986). An algorithm for generating necklaces of beads in two colors. Discrete Mathematics.
- Ruskey, F. (2003). Combinatorial Generation. University of Victoria.
MIT. Copyright (c) 2026 Amaar Chughtai.