Stable shuffle of a sequence

deterministic_shuffle.py

#!/usr/bin/env python3

from __future__ import annotations

import argparse
import random
from functools import reduce

from typing import Any

MASK32 = 0xFFFFFFFF


class LinearCongruentialGenerator:
    def __init__(self, seed: int = 0):
        # https://en.wikipedia.org/wiki/Linear_congruential_generator
        # Numerical Recipes, ranqd1, Chapter 7.1
        # https://roadrunnerwmc.github.io/blog/2020/05/08/nsmb-rng.html
        self.state = seed
        self.multiplier = 1664525
        self.increment = 1013904223

    def seed(self, seed: int) -> None:
        self.state = seed

    def random(self) -> int:
        self.state = (self.multiplier * self.state + self.increment) & MASK32
        return self.state

    def randbelow(self, n: int) -> int:
        maxsize = 1 << 32
        limit = maxsize - (maxsize % n)
        r = self.random()
        while r >= limit:
            r = self.random()
        return r % n

    def shuffle(self, x: list[Any]) -> None:
        for i in reversed(range(1, len(x))):
            # pick an element in x[:i+1] with which to exchange x[i]
            j = self.random() % (i + 1)
            x[i], x[j] = x[j], x[i]


def hash101(s: str) -> int:
    return reduce(lambda a, b: a * 101 + ord(b), s, 0) & MASK32


def demo(words: list[str], times: int, rng: Any) -> None:
    print(rng.__class__.__name__)
    for i in range(1, times + 1):
        these_words = words[:i] + [f"{i:02}"] + words[i:]
        wordlisthash = reduce(lambda a, b: a * 27644437 + hash101(b), these_words, 0)
        seed = (wordlisthash ^ wordlisthash >> 32) & MASK32
        rng.seed(seed)
        rng.shuffle(these_words)
        print(f'{i:2}: {", ".join(these_words)}')


def parse_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser(description="Stable Shuffle")
    parser.set_defaults(
        demo_words="Four score and seven years ago our forefathers".split(),
        demo_count=12,
        rng=LinearCongruentialGenerator,
    )
    parser.add_argument(
        "--lcg",
        "-L",
        action="store_const",
        const=LinearCongruentialGenerator,
        dest="rng",
        help="Use LinearCongruentialGenerator (default)",
    )
    parser.add_argument(
        "--random",
        "-R",
        action="store_const",
        const=random.Random,
        dest="rng",
        help="Use random.Random",
    )
    return parser.parse_args()


def main() -> int:
    args = parse_args()
    demo(args.demo_words, args.demo_count, args.rng())
    return 0


if __name__ == "__main__":
    exit(main())