randperm-crt

这是一个小型库，用于生成集合 {0, ..., n-1} 的随机排列，其中 n 是小素数幂的乘积，具有远小于 O(n) 的内存使用量。

将排列视为从 {0, ..., n-1} 到自身的函数 σ，此库还允许在常数时间内（与 i 无关）计算 σ(i) 和 σ^(-1)(i)。

工作原理

首先将 n 因式分解为素数幂，然后为 n 因子分解中的每个素数幂 q 生成 {0, ..., q-1} 的随机排列。然后使用中国剩余定理将来自这些“子排列”的每个元素组合合并成一个 {0, ..., n-1} 的排列。

何时不使用此库

如果需要以下任何一项，请不要使用此库

• 任何级别的随机性，而不仅仅是“看起来对用户来说像是随机的”。生成的排列非常“不是”无模式的，例如，可能会有所有数字模一个 n 的素数幂因子都相等的长时间序列。您可以使用 Composition 结构来组合多个排列，这样可以减少这种情况发生的可能性。
• 当 n 不是小素数幂的乘积时，在 n 个点上的随机排列。

示例

// 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));