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.
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, but a max number. The derived cycle should be part of the seed string to make sure we randomize the order again in each new cycle.
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 Python versions, as long as the same encoding and byte order are used.
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
FEISTEL_ROUNDS = 6
def get_feistel_index(
seed: str,
iteration: int,
size: int,
) -> 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(FEISTEL_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. Feistel is more appropriate if you need to calculate the index based on the same input and you're not interested in the rest of the list.
Thanks, AI. Today I learned something.