permutation-iterator

A Rust library for iterating over random permutations without fully materializing them into memory.

permutation-iterator lets you iterate over a random permutation, for example the values [0, 1, 2, 3, 4, 5] in a random order. It does so in constant space; it does not fully instantiate the values in memory then shuffle them.

Usage

Add this to your Cargo.toml:

[dependencies]
permutation_iterator = "0.1.2"

Example

Random, single integer range

Here is how to iterate over a random permutation of integers in the range [0, max), i.e. 0 inclusive to max exclusive. Every time you run this you will get a different permutation.

use permutation_iterator::Permutor;

fn main() {
    let max = 10;
    let permutor = Permutor::new(max);
    for permuted in permutor {
        println!("{}", permuted);
    }
}

Deterministic, single integer range

You can also pass in a key in order to iterate over a deterministically random permutation. Every time you run this you will get the same permutation:

use permutation_iterator::Permutor;

fn main() {
    let max = 10;
    let key: [u8; 32] = [0xBA; 32];
    let permutor = Permutor::new_with_slice_key(max, key);
    for permuted in permutor {
        println!("{}", permuted);
    }
}

Random, pair of integers

If you have e.g. two vectors of integers and you want to iterate over a random permutation of pairs from these lists you can use:

use permutation_iterator::RandomPairPermutor;

fn main() {
    let xs = [1, 2, 3];
    let ys = [4, 5, 6, 7, 8];

    let permutor = RandomPairPermutor::new(xs.len() as u32, ys.len() as u32);
    for (i, j) in permutor {
        println!("({}, {})", xs[i as usize], ys[j as usize]);
    }
}

Implementation details

One way of generating a random permutation is to shuffle a list. For example, given input integers [0, 1, 2, 3, 4, 5], one can shuffle it to e.g. [5, 3, 2, 0, 1, 4]. Each input element maps to one and only one output element, and vice versa (each output element maps to one and only one input element). As you consume the shuffled list from e.g. left to right you're consuming this random permutation.

Shuffling is O(n) time using the Fisher-Yates algorithm, however it is also O(n) space. We need a copy of the elements in-memory in order to shuffle them. This is inconvenient if the input range is large, or if the environment you're running on is memory-constrained.

Cryptography offers an alternative. Symmetric encryption boils down to mapping a given input to one and only one output, where the mapping is varied by a single secret key, and vice-versa (each output element maps to one and only one input element). If this bijective mapping did not exist we wouldn't be reliably able to retrieve the original input. One specific kind of symmetric encryption uses a block cipher (operating on n-bits at a time) implemented using a Feistel network.

A Feistel network is an extraordinary construct that allows you to use a simple, relatively weak non-invertible function over and over again and become a complicated, relatively strong invertible permutation. Hence in constant time we can encrypt inputs as a way of iterating over random permutations. We can similarly decrypt the output as a way of resuming permutations.

Consider the example of a bank that is trying to generate unique credit card numbers. Actual credit card numbers need to be stored very securely and we would rather not have to look them in order to find the next available number. By storing just a key and the last credit card number generated we can securely and efficiently continue iterating over the random permutation of all credit card numbers, without risking repeats.

License

permutation-iterator is distributed under the terms of the Apache License (Version 2.0). See LICENSE for details.