LyndonFactorizationLength
The factors in the Lyndon factorization.
✓ checked against that system · ! checked, with disagreements (hover a chip)FindStat
St001267via BinaryWord✓LyndonFactorizationLength(word)The factors in the Lyndon factorization.Typed signatures
| Type | Package | Applies |
|---|---|---|
(binary_word) -> number | combinatorics | always |
Details
- Defined over
BinaryWordas an expression in_x, evaluated by compute-engine — the definition IS the implementation. - Takes a
BinaryWordand nothing else — it reads values against their positions, or walks the orbits, so it needs the bijection. Applying it to a bare list is a type error, not a wrong answer. - FindStat's St001267. A factor starts at each position whose suffix is smaller than every earlier suffix; the table starts with a numeral above any suffix's, and pads a suffix with the digit 0, which is smaller than a letter, so the numerals order the suffixes.
Definition
Epsil, as the implementation runs it.
on BinaryWord, over _x
0 if Length(_x) < 1 else 1 if Length(_x) < 2 else Apply(
(v: list<integer>) => 1 +
Max(Sum(Map(
Function(1 if v[i + 1] <
Min(Map(Function(v[m], m), Range(1, i, 1))) else 0, i),
Range(2, Length(_x), 1),
)), 0),
Apply(
(a_init: list<integer>) => Fold(
(a: list<integer>, b) => Apply(
(a_next: list<integer>) => a_next,
Join(a, [Max(Sum(Map(Function((_x[b +
(m - 1)] +
1) *
3 ^
(Length(_x) - m), m), Range(1, Length(_x) - b +
1, 1))), 0)]),
),
a_init,
Range(1, Length(_x)),
),
[3 ^ Length(_x)],
),
)Examples
Properties #
About
| Examples | 4 |
|---|---|
| Crosswalk | FindStat |