API reference

shufflish.permutation(domain: int, seed: int | None = None, num_primes=3, allow_repetition=False, primes: Sequence[int] = shufflish.PRIMES) → AffineCipher

Return a permutation for the given domain, i.e., a random shuffle of range(domain). domain must be greater 0 and less than 2^63. seed determines which permutation is returned. A random seed is chosen if none is given.

The returned AffineCipher is iterable, indexable, and sliceable:

from shufflish import permutation
p = permutation(10)

for i in p:
    print(i)

print(list(p))
print(list(p[3:8]))
print(p[3])

Note the use of list. Where multiple values can be returned, iterators are used to conserve memory.

You can give a different set of primes to choose from, though the default set should work for most values of domain, and the selection process is pretty robust:

  1. Remove primes that are not coprime, i.e., gcd(domain, prime) = 1. Testing that prime is not a factor of domain is sufficient.

  2. Remove duplicates prime % domain. In modular arithmetic, multiplication with prime and prime % domain produces the same result, so we use only one prime from each congruence class to improve uniqueness of permutations.

  3. Select the seed-th combination of num_primes primes. If allow_repetition=False (default), repeated combinations are skipped.

Note

If you can afford a tiny chance of repeated permutations, you can use allow_repetition=True to significantly speed up this function. Empirically, we find that the first repetition occurs at earliest after domain seeds. If you need a lot of permutations for the same domain and cannot afford repetitions, consider the Permutations class, which generates all coprimes ahead of time.

class shufflish.Permutations(domain: int, num_primes=3, allow_repetition=False, primes: Sequence[int] = shufflish.PRIMES)

Create many permutations for the given domain, i.e., a random shuffle of range(domain), with fixed settings. domain must be greater 0 and less than 2^63. The returned AffineCipher is iterable, indexable, and sliceable:

from shufflish import Permutations
perms = Permutations(10)
p = perms.get()

for i in p:
    print(i)

print(list(p))
print(list(p[3:8]))
print(p[3])

See the permutation() function for details on how this works.

Note

This class can be a good choice to create many permutations in the same domain. It pre-calculates and stores all coprimes, so creating permutations is much faster than the permutation() function. Beware that, especially for larger than default values of num_primes, this can occupy a lot of memory. The default settings use roughly 1.3 MiB.

class shufflish.AffineCipher(domain: int, prime: int, pre_offset: int, post_offset: int)

The base class returned by permutation() and Permutations. Produces indices from a permutation of range(domain). You can iterate over all indices, get a range, or access randomly:

from shufflish import AffineCipher
p = AffineCipher(10, 7, 6, 3)

for i in p:
    print(i)

print(list(p))
print(list(p[3:8]))
print(p[3])

Internally, it maps an index i to ((i + pre_offset) * prime + post_offset) % domain. This produces a permutation of range(domain) if the following are true:

  • prime and domain are coprime, i.e., gcd(domain, prime) = 1

  • prime, pre_offset, post_offset < domain

  • 0 < domain < 2**63 to avoid division by zero and overflows.

The advantage is that there is no setup time, an instance occupies just 48 bytes, and it runs 20 times faster than random.shuffle() and twice as fast as numpy.random.shuffle(). It is also ten times faster than random.randrange(), which obviously does not produce a permutation.

shufflish.local_shuffle(iterable: Iterable, chunk_size: int = 16384, seed=None) → Generator[int]

Retrieve chunks of the given chunk_size from iterable, perform a true shuffle on them, and finally, yield individual values from the shuffled chunks. seed is used to seed the random generator for the shuffle operation.

shufflish.PRIMES = (18446744073709551557, 18446744073709551533, 18446744073709551521, 18446744073709551437, 18446744073709551427, 18446744073709551359, 18446744073709551337, 18446744073709551293, 18446744073709551263, 18446744073709551253, 18446744073709551191, 18446744073709551163, 18446744073709551113, 18446744073709550873, 18446744073709550791, 18446744073709550773, 18446744073709550771, 18446744073709550719, 18446744073709550717, 18446744073709550681, 18446744073709550671, 18446744073709550593, 18446744073709550591, 18446744073709550539, 18446744073709550537, 18446744073709550381, 18446744073709550341, 18446744073709550293, 18446744073709550237, 18446744073709550147, 18446744073709550141, 18446744073709550129, 18446744073709550111, 18446744073709550099, 18446744073709550047, 18446744073709550033, 18446744073709550009, 18446744073709549951, 18446744073709549861, 18446744073709549817, 18446744073709549811, 18446744073709549777, 18446744073709549757, 18446744073709549733, 18446744073709549667, 18446744073709549621, 18446744073709549613, 18446744073709549583, 18446744073709549571, 18446744073709549519, 18446744073709549483, 18446744073709549441, 18446744073709549363, 18446744073709549331, 18446744073709549327, 18446744073709549307, 18446744073709549237, 18446744073709549153, 18446744073709549123, 18446744073709549067, 18446744073709549061, 18446744073709549019, 18446744073709548983, 18446744073709548899, 18446744073709548887, 18446744073709548859, 18446744073709548847, 18446744073709548809, 18446744073709548703, 18446744073709548599, 18446744073709548587, 18446744073709548557, 18446744073709548511, 18446744073709548503, 18446744073709548497, 18446744073709548481, 18446744073709548397, 18446744073709548391, 18446744073709548379, 18446744073709548353, 18446744073709548349, 18446744073709548287, 18446744073709548271, 18446744073709548239, 18446744073709548193, 18446744073709548119, 18446744073709548073, 18446744073709548053, 18446744073709547821, 18446744073709547797, 18446744073709547777, 18446744073709547731, 18446744073709547707, 18446744073709547669, 18446744073709547657, 18446744073709547537, 18446744073709547521, 18446744073709547489, 18446744073709547473, 18446744073709547471)

The default set of primes used by permutation() and Permutations.