# Crate rand_unique

source ·## Expand description

## rand-unique

A no-std crate for generating sequences of unique random numbers in O(1) time and space. `RandomSequence`

is a non-repeating pseudo-random sequence generator, directly index-able for the nth number in the sequence.

Not cryptographically secure. No-std compatible.

Properties of each `RandomSequence`

:

**Unique:**The sequence will only include each number once; every index has a unique output.**Uniform:**The sequence is pseudo-uniformly distributed. Each number which has not yet appeared in the sequence has a roughly equal probability of being the next number in the sequence.**Fast:**Computing the value for any random index in the sequence is an O(1) operation in time and memory complexity.**Indexable:**`RandomSequence::n(index)`

returns the output for a given position in the sequence.**Integer Range:**Support for`u8`

,`u16`

,`u32`

,`u64`

, and`usize`

. Outputs can be cast to`i8`

,`i16`

,`i32`

,`i64`

, and`isize`

respectively.**Terminating and Wrapping:**Iterator usage of`RandomSequence::next()`

will terminate at the end of the sequence. Alternatively,`RandomSequence::wrapping_next()`

will wrap around to the start of the sequence when exhausted.**Deterministic:**The sequence is deterministic and repeatable for the same seeds.`RandomSequenceBuilder`

can be serialized with serde to store the sequence parameters. Must have the`serde`

feature enabled.`RandomSequenceBuilder::new(seed_base, seed_offset)`

can be used to instantiate with specific seeds.`RandomSequenceBuilder::rand(prng)`

can be used to instantiate with random seeds. Must have the`rand`

feature enabled.`RandomSequenceBuilder::into_iter()`

constructs a`RandomSequence`

with the parameters defined by the builder. Two builders configured the same will generate the same sequence, and so we can construct multiple iterators over the same sequence.

### Features

This crate is no-std compatible.

`default-features`

:`rand`

`rand`

: Enables the`rand(&mut RngCore)`

helper methods on`RandomSequenceBuilder`

and`RandomSequence`

to initialize with random seeds, which requires the`rand`

dependency. Can be omitted and instead manually provide seeds to the`RandomSequenceBuilder::seed()`

method to instantiate.`serde`

: Enables serde`Serlialize`

and`Deserialize`

support for`RandomSequenceBuilder`

, which requires the`serde`

dependency.

### Example

```
use std::collections::HashSet;
use rand::rngs::OsRng;
use rand_unique::{RandomSequence, RandomSequenceBuilder};
// Initialise a sequence from a random seed.
let config = RandomSequenceBuilder::<u16>::rand(&mut OsRng);
let mut sequence: RandomSequence<u16> = config.into_iter();
// Iterate over the sequence with next() and prev(), or index directly with n(i).
assert_eq!(sequence.next().unwrap(), sequence.n(0));
assert_eq!(sequence.next().unwrap(), sequence.n(1));
assert_eq!(sequence.next().unwrap(), sequence.n(2));
// Get the current index, if the sequence is not yet exhausted.
assert_eq!(sequence.index(), Some(3));
assert!(!sequence.exhausted());
// Initialise a new RandomSequence iterator over the same sequence.
let sequence_2 = config.into_iter();
assert_eq!(sequence_2.n(0), sequence.n(0));
assert_eq!(sequence_2.index(), Some(0));
// Consume the iterator, and show outputs are unique across the entire type.
// With support for u8, u16, u32, u64, and usize.
let nums: HashSet<u16> = sequence_2.collect();
assert_eq!(nums.len(), u16::MAX as usize + 1);
// Serialise the config to reproduce the same sequence later.
// Requires the "serde" feature to be enabled.
// let config = serde_json::to_string(&sequence.config).unwrap();
```

### Output Distribution

Future work could include a more rigorous analysis of the output distribution. For now, the following charts demonstrate the roughly uniform distribution for `RandomSequence<u16>`

.

Histogram visualisation of the `RandomSequence`

output distribution.

Visual scatter plot of the `RandomSequence`

output.

### How It Works

This non-repeating pseudo-random number generator works by creating a permutation function against the index in the sequence, herein referred to as `x`

. So for any position `x`

in the sequence, we want to deterministically compute a unique output number via function `n(x)`

, where comparing `n(x)`

and `n(x + 1)`

would appear randomly generated.

For any prime number $p$ which satisfies $p 3 \mod 4$, then for any input $x$, the operation $f(x) = x^2 \mod p$ will produce a unique number for each value of $x$ where $2x < p$.

Quadratic residue tends to cluster numbers together, and so we apply the quadratic residue permutation along with other permutation functions (*wrapping* addition and xor) to add further noise. Permutation functions are those with a direct 1-1 mapping for all inputs to outputs, where each input has a unique output.

In a simplified form, the permutation function is:

```
/// `p` is chosen to be the largest number satisfying:
/// - a prime number
/// - that satisfies p = 3 mod 4 (`p % 4 == 3`)
/// - that fits in the datatype chosen, in this example `u64`
const PRIME: u64 = 18446744073709551427;
/// Simplified example of the quadratic residue function, taking input `x` for prime `PRIME`.
fn permute_qpr(x: u64) -> u64 {
// we choose x to be the largest prime number of the type, and so there are a small handful
// of numbers in the datatype which are larger than p. We map them directly to themselves.
if x > PRIME {
return x;
}
// compute the residue, in the real method we're careful to avoid integer overflow, omitted here
// for clarity.
let residue = (x * x) % PRIME;
// the residue is unique for all x <= p/2; and so p-residue is also unique for x > p/2.
if x <= PRIME / 2 {
residue
} else {
PRIME - residue
}
}
/// Randomly selected variables to introduce further noise in the output generation.
const OFFSET_NOISE: u64 = 0x46790905682f0161;
const XOR_NOISE: u64 = 0x5bf0363546790905;
/// We can then use this permutation function [permute_qpr] to build our number generator `n(x)`.
fn n(x: u64) -> u64 {
// function sequence: permute_qpr, wrapping addition, xor, permute_qpr
// care is taken in the real implementation to use wrapping addition, omitted here for clarity.
permute_qpr((permute_qpr(x) + OFFSET_NOISE) ^ XOR_NOISE)
}
```

### Sources

Based on the article by @preshing using quadratic prime residue:

- Article: http://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/
- Source: https://github.com/preshing/RandomSequence/blob/master/randomsequence.h

## Structs

- Generate a deterministic pseudo-random sequence of unique numbers.
- The configuration for RandomSequence, a random unique sequence generator.