Shiloach's least rotation algorithm in Python

Canonizes a circular string by repeatedly eliminating non-minimal candidate rotations.

File: shiloach_least_rotation.py, 68 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

shiloach_least_rotation.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/shiloach-least-rotation/. The authors are listed in prov/WKJHV4.jsonl.

from collections.abc import Sequence
from typing import Protocol, TypeVar


class Ordered(Protocol):
    def __lt__(self, other: "Ordered", /) -> bool: ...


T = TypeVar("T", bound=Ordered)


def least_rotation_index(s: Sequence[T]) -> int:
    """Return the smallest 0-based index i at which the least rotation of s starts.

    The rotation at i is s[i:] + s[:i]. Letters need a total order and are
    compared with == and <. Precondition: none; the empty sequence gives 0.
    Cost: fewer than 3 * len(s) letter comparisons, O(1) extra space.
    """
    n = len(s)
    if n == 0:
        return 0
    g, h = 0, 1  # @line L1
    while h < n:  # @line L2
        k = 0  # @line L3
        while k < n and s[(g + k) % n] == s[(h + k) % n]:  # @line L4
            k += 1  # @line L5
        if k == n:  # @line L6
            return g
        if s[(g + k) % n] < s[(h + k) % n]:  # @line L7
            h = h + k + 1  # @line L8
        else:  # @line L9
            g = max(h, g + k + 1)  # @line L10
            h = g + 1  # @line L11
    return g  # @line L12


def least_rotation(s: str) -> str:
    """Return the lexicographically least rotation of the string s."""
    i = least_rotation_index(s)
    return s[i:] + s[:i]


def least_rotation_starts(s: Sequence[T]) -> list[int]:
    """Return all 0-based indices where the least rotation of s starts, in increasing order.

    They are g, g + d, g + 2d, ... below len(s), where g is the smallest one
    and d is the length of the primitive root of s. Cost: O(len(s)).
    """
    n = len(s)
    if n == 0:
        return []
    g = least_rotation_index(s)
    # smallest period d of s that divides n, from the prefix function
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    d = n - pi[n - 1]
    if n % d != 0:
        d = n
    return list(range(g, n, d))

test_shiloach_least_rotation.py 95 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/shiloach-least-rotation/. The authors are listed in prov/WKJHV4.jsonl.

import itertools
import random

from shiloach_least_rotation import (
    least_rotation,
    least_rotation_index,
    least_rotation_starts,
)


def brute_index(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    return min(range(n), key=lambda i: (s[i:] + s[:i], i))


def brute_starts(s: str) -> list[int]:
    n = len(s)
    if n == 0:
        return []
    best = min(s[i:] + s[:i] for i in range(n))
    return [i for i in range(n) if s[i:] + s[:i] == best]


def test_example() -> None:
    assert least_rotation_index("bbaaccaadd") == 2
    assert least_rotation("bbaaccaadd") == "aaccaaddbb"
    assert least_rotation_index("acabacab") == 2
    assert least_rotation_starts("acabacab") == [2, 6]


def test_edges() -> None:
    assert least_rotation_index("") == 0
    assert least_rotation_starts("") == []
    assert least_rotation_index("z") == 0
    assert least_rotation_index("aaaa") == 0
    assert least_rotation_starts("aaaa") == [0, 1, 2, 3]
    assert least_rotation_index("ba") == 1
    assert least_rotation_index("cabbage") == 1
    assert least_rotation_index("aaaaaaabaa") == 8
    assert least_rotation_index([3, 1, 2, 1, 2]) == 1


def test_exhaustive_small() -> None:
    for alphabet, top in (("a", 8), ("ab", 12), ("abc", 8)):
        for n in range(top + 1):
            for t in itertools.product(alphabet, repeat=n):
                s = "".join(t)
                assert least_rotation_index(s) == brute_index(s), s
                assert least_rotation_starts(s) == brute_starts(s), s


def test_random_against_brute_force() -> None:
    rng = random.Random(20261106)
    for trial in range(1500):
        alphabet = "abc"[: 1 + trial % 3]
        n = rng.randrange(0, 40)
        if trial % 5 == 0 and n > 0:
            block = "".join(rng.choice(alphabet) for _ in range(rng.randrange(1, 5)))
            s = (block * n)[:n] if rng.random() < 0.5 else block * (1 + n % 4)
        else:
            s = "".join(rng.choice(alphabet) for _ in range(n))
        assert least_rotation_index(s) == brute_index(s), s
        assert least_rotation_starts(s) == brute_starts(s), s
        assert least_rotation(s) == min((s[i:] + s[:i] for i in range(len(s))), default="")


class Counted:
    count = 0

    def __init__(self, c: str) -> None:
        self.c = c

    def __eq__(self, other: object) -> bool:
        Counted.count += 1
        return isinstance(other, Counted) and self.c == other.c

    def __lt__(self, other: "Counted") -> bool:
        return self.c < other.c

    __hash__ = None  # type: ignore[assignment]


def test_comparison_bound() -> None:
    rng = random.Random(7)
    words = ["a" * k + "baa" for k in range(20)]
    words += ["".join(rng.choice("ab") for _ in range(rng.randrange(1, 60))) for _ in range(300)]
    for s in words:
        Counted.count = 0
        least_rotation_index([Counted(c) for c in s])
        assert Counted.count < 3 * len(s), s

What the next level needs

the tests did not run in this build

Read the full page about Shiloach's least rotation algorithm