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 80 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.

Warning

This class only performs numerical overflow checks during initialization. If you choose to create instances yourself instead of through the permutation() function or Permutations class, you need to ensure that the parameters fulfill the listed requirements.

expand(self) → shufflish.AffineCipher

Return a new cipher with the same parameters, but slice extents are set to their initial values (0, domain, 1).

extents() → slice

Returns the extents (start, stop, step) of this instance as a slice.

Note

stop may not be the exact value you expect. E.g., for a cipher p and slice p[:10::2] you might expect 10, but you will get 9 instead. That is because this slice ends at index 8 and stop always points to the next index (or previous if iterating backwards). This is necessary to make p[:10::2][::-1] and similar behave like a tuple or list in the same situation.

index(value) → int

Return the index of value.

Raises ValueError if the value is not present.

invert() → shufflish.AffineCipher

Returns the inverse of this affine cipher, i.e., if p is an AffineCipher and ip = p.invert(), then ip[p[x]] = x for all valid inputs x.

Note

Slices cannot be inverted currently. Use AffineCipher.expand() to obtain the full permutation first.

is_slice(self) → bool

Returns True if this cipher represents a slice, and False if it covers the full permutation.

parameters() → tuple[domain, prime, pre_offset, post_offset]

Returns the affine parameters as tuple (domain, prime, pre_offset, post_offset).

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

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. They are the 100 largest primes that can be represented by a 64bit unsigned integer.