Efficient O(1)-space pseudorandom permutation for large scale shuffling
Project description
smallperm
Small library to generate permutations of a list of elements using pseudo-random permutations (PRP). Uses O(1)
memory and O(1)
time to generate the next element of the permutation.
>>> from smallperm import PseudoRandomPermutation
>>> list(PseudoRandomPermutation(42, 0xDEADBEEF))
[14, 32, 25, 16, 0, 12, 5, 37, 30, 7, 40, 17, 27, 35, 21, 15, 1, 13, 38, 4, 9, 36, 20, 22, 24, 39, 41, 19, 3, 18, 8, 2, 29, 31, 6, 34, 11, 23, 26, 10, 28, 33]
API
-
Initialization:
PseudoRandomPermutation(length: int, seed: int)
- Generates a permutation of
[0, length)
usingseed
.
- Generates a permutation of
-
Usage: Iterate over the instance to get the next element of the permutation.
- Example:
list(PseudoRandomPermutation(42, 0xDEADBEEF))
- Example:
-
O(1) forward/backward mapping:
forward(i: int) -> int
: Returns thei
-th element of the permutation.backward(el: int) -> int
: Returns the index ofel
in the permutation.
Acknowledgements
Gratefully reuses code from https://github.com/asimihsan/permutation-iterator-rs which does most of the heavy lifting. Because the heavy lifting is done in Rust, this library is very efficient.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
smallperm-0.1.8.tar.gz
(20.3 kB
view hashes)
Built Distributions
Close
Hashes for smallperm-0.1.8-cp37-abi3-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fafaf2a75994b3f251b2f2765aec64a02e5a38c263c20d2d71bb53a831a976e7 |
|
MD5 | def336dd05b16cd2a530bd105c32c238 |
|
BLAKE2b-256 | 309dfc81b3dc7f8df2d6e26a0a3620b8b40437557544ab2b1cd946def570c4e4 |
Close
Hashes for smallperm-0.1.8-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a12fa9c8c761be4241e9145c794e13b3e737abccef3e0c13f383b22832c8b5df |
|
MD5 | 79b068c242c0573e8fd81468eb4032d7 |
|
BLAKE2b-256 | 56ec5c9fd9a8eddbc4f22630d61e36cb7a438ed459acbb6feaecc636d1fa96b9 |
Close
Hashes for smallperm-0.1.8-cp37-abi3-macosx_10_12_x86_64.macosx_11_0_arm64.macosx_10_12_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6d17fb524a4db452965d3a29dedc41064a67bb7558e74104a0a6aa9bc3d43200 |
|
MD5 | 0759aa9e84863d7d2011544d9928596a |
|
BLAKE2b-256 | 808864cb79fe8d37d690a49bb7e9e2f330cf779db8f0581fe83e04655d875889 |