CAT necklace generation in Python
Generates necklaces in constant amortized time per necklace.
- File
cattell_necklace_generation.py, 74 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/cattell-necklace-generation/. The authors are listed in prov/QYDXYF.jsonl.
"""Recursive CAT generation of prenecklaces, necklaces and Lyndon words.
The recursion GEN(t, p) of Cattell, Ruskey, Sawada, Serra and Miers is run
with an explicit stack, so the depth n does not hit the Python call limit.
"""
from typing import Iterator, List, Tuple
def prenecklaces(k: int, n: int) -> Iterator[Tuple[Tuple[int, ...], int]]:
"""Yield (a, p) for every prenecklace a of length n over {0, ..., k-1}.
Precondition: k >= 1 and n >= 1. The words come in increasing
lexicographic order, and p is the length of the longest Lyndon prefix
of a. Cost: O(1) amortized per necklace for k >= 2, plus O(n) per word
for the tuple that is yielded.
"""
if k < 1 or n < 1:
raise ValueError("need k >= 1 and n >= 1")
a = [0] * n
# A frame [t, p, c] stands for the call GEN(t, p) on the prefix a[0 .. t-1];
# c is the next letter to try at index t. The frame with t = 0 is line L1.
stack: List[List[int]] = [[0, 1, 0]]
while stack:
frame = stack[-1]
t, p, c = frame
# @line L2
if t == n:
# @line L3
yield tuple(a), p
stack.pop()
continue
if t == 0:
# @line L1
lo = 0
else:
# @line L4
lo = a[t - p]
if c < lo:
c = lo
# @line L6
if c > k - 1:
stack.pop()
continue
a[t] = c
frame[2] = c + 1
if t > 0 and c == a[t - p]:
# @line L5
stack.append([t + 1, p, 0])
else:
# @line L7
stack.append([t + 1, t + 1, 0])
def necklaces(k: int, n: int) -> List[Tuple[int, ...]]:
"""All necklaces of length n over {0, ..., k-1}, in increasing order."""
return [a for a, p in prenecklaces(k, n) if n % p == 0]
def lyndon_words(k: int, n: int) -> List[Tuple[int, ...]]:
"""All Lyndon words of length n over {0, ..., k-1}, in increasing order."""
return [a for a, p in prenecklaces(k, n) if p == n]
def count_calls(k: int, n: int) -> int:
"""The number of calls of GEN in one run, including the root (line L1)."""
calls = 1
for t in range(1, n + 1):
# each call GEN(t, p) is one prenecklace of length t
calls += sum(1 for _ in prenecklaces(k, t))
return calls
test_cattell_necklace_generation.py 125 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/cattell-necklace-generation/. The authors are listed in prov/QYDXYF.jsonl.
import itertools
import random
from math import gcd
from typing import List, Tuple
from cattell_necklace_generation import count_calls, lyndon_words, necklaces, prenecklaces
Word = Tuple[int, ...]
def rotations(w: Word) -> List[Word]:
return [w[i:] + w[:i] for i in range(len(w))]
def is_necklace(w: Word) -> bool:
return all(w <= r for r in rotations(w))
def is_lyndon(w: Word) -> bool:
return len(w) > 0 and all(w < r for r in rotations(w)[1:])
def lyn(w: Word) -> int:
return max(q for q in range(1, len(w) + 1) if is_lyndon(w[:q]))
def is_prenecklace(w: Word, k: int) -> bool:
n = len(w)
for q in range(1, n + 1):
for u in itertools.product(range(k), repeat=q):
if is_lyndon(u) and all(w[i] == u[i % q] for i in range(n)):
return True
return False
def phi(m: int) -> int:
return sum(1 for i in range(1, m + 1) if gcd(i, m) == 1)
def necklace_count(k: int, n: int) -> int:
return sum(phi(d) * k ** (n // d) for d in range(1, n + 1) if n % d == 0) // n
def test_example() -> None:
got = [("".join(map(str, a)), p) for a, p in prenecklaces(2, 4)]
assert got == [
("0000", 1),
("0001", 4),
("0010", 3),
("0011", 4),
("0101", 2),
("0110", 3),
("0111", 4),
("1111", 1),
]
assert len(necklaces(2, 4)) == 6
assert [("".join(map(str, a))) for a in lyndon_words(2, 4)] == ["0001", "0011", "0111"]
assert count_calls(2, 4) == 19
def test_edge_cases() -> None:
assert list(prenecklaces(1, 1)) == [((0,), 1)]
assert necklaces(1, 500) == [(0,) * 500]
assert lyndon_words(1, 500) == []
assert lyndon_words(1, 1) == [(0,)]
assert necklaces(3, 1) == [(0,), (1,), (2,)]
for bad in ((0, 3), (2, 0)):
try:
list(prenecklaces(*bad))
except ValueError:
pass
else:
raise AssertionError("expected ValueError")
def test_exhaustive_small() -> None:
for k in (1, 2, 3):
for n in range(1, 7 if k < 3 else 6):
got = list(prenecklaces(k, n))
words = [a for a, _ in got]
assert words == sorted(set(words))
all_words = list(itertools.product(range(k), repeat=n))
assert words == [w for w in all_words if is_prenecklace(w, k)]
for a, p in got:
assert p == lyn(a)
assert necklaces(k, n) == [w for w in all_words if is_necklace(w)]
assert lyndon_words(k, n) == [w for w in all_words if is_lyndon(w)]
assert len(necklaces(k, n)) == necklace_count(k, n)
def test_cat_bound() -> None:
for k in (2, 3):
for n in range(1, 12 if k == 2 else 8):
calls = count_calls(k, n)
bound = 2 * (k / (k - 1)) ** 2 * k**n / n + n * (n + 1) * k ** (n / 2) + 1
assert calls <= bound
assert calls <= 4 * (k / (k - 1)) ** 2 * len(necklaces(k, n)) + n * (n + 1) * k ** (n / 2) + 1
def test_random() -> None:
rng = random.Random(7)
cache = {}
for _ in range(600):
k = rng.choice((1, 2, 3))
n = rng.randint(1, 8 if k < 3 else 6)
if (k, n) not in cache:
cache[(k, n)] = (set(necklaces(k, n)), set(lyndon_words(k, n)))
neck, lyn_set = cache[(k, n)]
w = tuple(rng.randrange(k) for _ in range(n))
assert (w in neck) == is_necklace(w)
assert (w in lyn_set) == is_lyndon(w)
m = min(rotations(w))
assert m in neck
if __name__ == "__main__":
test_example()
test_edge_cases()
test_exhaustive_small()
test_cat_bound()
test_random()
print("ok")
What the next level needs
- the tests did not run in this build