stouputils.collections.shuffle module#

affine_permutation_generator(
n: int,
seed: int = 0,
) → Generator[int][source]#

Generate a memory-efficient pseudo-random permutation of [0, n).

Each i in [0, n) can only be visited once thanks to the affine bijection: (a*i + b) % n where a and b are random integers and coprime with n.

Parameters:

  • n (int) – Number of elements to visit.

  • seed (int) – Random seed for reproducibility.

Yields:

Generator[int] – A random permutation of [0, n).

>>> list(affine_permutation_generator(10))
[6, 3, 0, 7, 4, 1, 8, 5, 2, 9]
>>> list(affine_permutation_generator(10, seed=42))
[4, 5, 6, 7, 8, 9, 0, 1, 2, 3]

Make sure all elements are visited: >>> sorted(list(affine_permutation_generator(100, seed=42))) == list(range(100)) True

We can have infinite permutations without blowing up memory: >>> for i, perm in enumerate(affine_permutation_generator(100**2000)): … if i > 4: break … print(f”Permutation {i}: {str(perm)[:20]}…”) Permutation 0: 60923891346657165714… Permutation 1: 77383182119683752460… Permutation 2: 93842472892710339206… Permutation 3: 10301763665736925951… Permutation 4: 26761054438763512697…

feistel_permutation_generator(
n: int,
seed: int = 0,
) → Generator[int][source]#

Generate a memory-efficient pseudo-random permutation of [0, n).

This uses a Feistel network to build a bijective mapping over a power-of-two domain, then filters values outside [0, n).

Unlike affine permutations, this produces a much more “shuffle-like” order with significantly reduced algebraic structure.

Parameters:

  • n (int) – Number of elements to visit.

  • seed (int) – Random seed for reproducibility.

Yields:

Generator[int] – A pseudo-random permutation of [0, n).

>>> list(feistel_permutation_generator(10))
[1, 8, 0, 5, 3, 6, 9, 7, 4, 2]
>>> list(feistel_permutation_generator(10, seed=42))
[5, 3, 1, 6, 4, 2, 8, 0, 9, 7]

Make sure all elements are visited: >>> sorted(list(feistel_permutation_generator(100, seed=42))) == list(range(100)) True

We can have infinite permutations without blowing up memory: >>> for i, perm in enumerate(feistel_permutation_generator(100**2000)): … if i > 4: break … print(f”Permutation {i}: {str(perm)[:20]}…”) Permutation 0: 56877730339930604433… Permutation 1: 31140272880303506593… Permutation 2: 89677538354424247341… Permutation 3: 94477358131828883980… Permutation 4: 37089694092416945146…

class FeistelHelpers[source]#

Bases: object

Helper functions for the Feistel permutation generator.

static round_prf(
seed: int,
round_no: int,
value: int,
out_bits: int,
) → int[source]#

Small deterministic Pseudo-Random Function (PRF) used inside the Feistel network.

Parameters:

  • seed (int) – Seed for the PRF.

  • round_no (int) – Round number (0-3).

  • value (int) – Input value.

  • out_bits (int) – Output bit-width.

Returns:

The PRF output.

Return type:

int

static permute(
x: int,
seed: int,
bits: int,
rounds: int = 4,
) → int[source]#

Feistel permutation over a fixed bit-width domain.

Parameters:

  • x (int) – Input value.

  • seed (int) – Random seed for the permutation.

  • bits (int) – Bit-width of the domain.

  • rounds (int) – Number of rounds to apply (default: 4).

Returns:

Permuted value.

Return type:

int