randperm-crt

Small library for generating random permutations of the set {0, ..., n-1} where n is a product of small prime powers, with much less than O(n) memory usage.

Thinking of a permutation as a function σ from {0, ..., n-1} to itself, this library also allows for computation of σ(i) and σ^(-1)(i) in constant time (independent of i).

How it works

First n is factored into prime powers, and random permutations of {0, ..., q-1} are generated for each prime power q in the factorization of n. Then the Chinese Remainder Theorem is used to combine each combination of elements from these "sub-permutations" into a permutation of {0, ..., n-1}.

When not to use this

Don't use this if you need any of the following:

• Any level of randomness beyond "it looks kind of random to the user". The permutations generated are very much not "patternless", for example there can (and will) be long streaks of numbers that are all equal modulo a prime power factor of n. You can use the Composition struct to compose multiple permutations which can reduce the chance of this happening.
• Random permutations on n points where n is not the product of small prime powers.

Example

// Create a permutation on 11! points.
let factorial_11 = (1..=11).product();
let perm = RandomPermutation::new(factorial_11).unwrap();

// Calculate the image of 0, 1, 2, ..., 99 under the permutation.
let image = perm.iter().take(100).collect::<Vec<_>>();
println!("{image:?}");

// Find `i` such that the image of `i` is 0.
let i = perm.inverse().nth(0).unwrap();
assert_eq!(perm.nth(i), Some(0));