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