Shuffling: Fisher-Yates vs Feistel

---

I'm working on the problem of picking a random word from a list of words. Given a list of 10 words, I want each word to be picked exactly once within every block of 10 picks. For picks 11 through 20, I want the same words in a different order. Sounds simple, right?

I have little formal training in mathematics, but these days we can use AI to help us determine how to solve these types of problems and learn something in the process.

Inputs

If I break the problem down, I start with four parameters: a list of words, a seed, a cycle, and an iteration. Based on these, we should be able to create something that returns the same word for the same inputs.

The cycle does not need to be an input. Given the continuously increasing iteration and the number of words, we can derive both the cycle and the position within it using mod, based on the length. That leaves us with only three inputs: words, seed, and iteration.

Technically we don't even need to send a list of words, the size of the list is enough (as an index is the number between 0 and the size).

The cycle must be part of the seed string to make sure we randomize differently between cycles.

Fisher-Yates

The Fisher-Yates algorithm shuffles a copy of the complete list. We can then return the word at the requested position. Deriving swaps from SHA-256 makes the result reproducible across systems and Python versions.

import hashlib


def fisher_yates_word(
    words: list[str],
    seed: str,
    iteration: int,
) -> str:
    def stable_random_below(upper_bound: int, swap_index: int) -> int:
        nonce = 0
        hash_range = 1 << hashlib.sha256().digest_size * 8
        unbiased_limit = hash_range - hash_range % upper_bound

        while True:
            value = (
                f"{cycle_seed}:swap:{swap_index}:nonce:{nonce}"
                .encode("utf-8")
            )
            number = int.from_bytes(hashlib.sha256(value).digest(), "big")
            if number < unbiased_limit:
                return number % upper_bound
            nonce += 1

    if not words:
        raise ValueError("words must not be empty")
    if iteration < 0:
        raise ValueError("iteration must not be negative")

    cycle, cycle_iteration = divmod(iteration, len(words))
    cycle_seed = f"{seed}:cycle:{cycle}"
    shuffled = words.copy()

    for index in range(len(shuffled) - 1, 0, -1):
        swap_index = stable_random_below(index + 1, index)
        shuffled[index], shuffled[swap_index] = (
            shuffled[swap_index],
            shuffled[index],
        )

    return shuffled[cycle_iteration]


word = fisher_yates_word(
    words=["alpha", "bravo", "charlie"],
    seed="my-seed",
    iteration=3,
)
print(word)

Feistel

So what if we only need one word and do not want to create a shuffled copy of the complete list? Let's use a Feistel network combined with cycle walking. It calculates a permuted list index from the combined seed, position, and list size.

We repeat the Feistel step six times to mix the values thoroughly.

import hashlib


def get_feistel_index(
    seed: str,
    iteration: int,
    size: int,
    rounds: int = 6,
) -> int:
    def round_function(value: int, round_number: int, mask: int) -> int:
        message = f"{seed}:{round_number}:{value}".encode("utf-8")
        digest = hashlib.sha256(message).digest()
        return int.from_bytes(digest, "big") & mask

    def feistel_permute(value: int, domain_bits: int) -> int:
        half_bits = domain_bits // 2
        half_mask = (1 << half_bits) - 1
        left = value >> half_bits
        right = value & half_mask

        for round_number in range(rounds):
            left, right = (
                right,
                left ^ round_function(right, round_number, half_mask),
            )

        return (left << half_bits) | right

    if size <= 0:
        raise ValueError("size must be greater than zero")
    if not 0 <= iteration < size:
        raise ValueError(f"iteration must be in [0, {size})")

    domain_bits = max(2, (size - 1).bit_length())
    if domain_bits % 2:
        domain_bits += 1

    index = iteration

    # Cycle-walking skips values outside the list length.
    while True:
        index = feistel_permute(index, domain_bits)
        if index < size:
            return index


def feistel_word(
    words: list[str],
    seed: str,
    iteration: int,
) -> str:
    if not words:
        raise ValueError("words must not be empty")
    if iteration < 0:
        raise ValueError("iteration must not be negative")

    cycle, cycle_iteration = divmod(iteration, len(words))
    cycle_seed = f"{seed}:cycle:{cycle}"
    index = get_feistel_index(cycle_seed, cycle_iteration, len(words))
    return words[index]


word = feistel_word(
    words=["alpha", "bravo", "charlie"],
    seed="my-seed",
    iteration=3,
)
print(word)

Final thoughts

Fisher-Yates is a great solution if you need to work with the entire list, which is appropriate if you need to know about a significant portion of the sequence of numbers. Feistel is more appropriate if you need to calculate the index based on the same input and you're not interested in other numbers.

Thanks, AI. Today I learned something.