lyndon-words

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.

What is this?

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.

Install

pip install lyndon-words

Quick start

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(...)))

Word representation

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.

API

Enumeration and generation functions take keyword-only alphabet_size and length.

alphabet_size >= 1 and length >= 1 are required; otherwise a ValueError is raised.

Definitions

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.

References

• 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.

License

MIT. Copyright (c) 2026 Amaar Chughtai.