Crates.io | randperm-crt |

lib.rs | randperm-crt |

version | 0.1.1 |

source | src |

created_at | 2023-08-18 02:34:24.17311 |

updated_at | 2023-08-19 18:35:33.677861 |

description | Small library for generating random permutations |

homepage | |

repository | https://github.com/benwh1/randperm-crt/ |

max_upload_size | |

id | 947525 |

size | 19,326 |

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`

).

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

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.

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