permutation-iterator-rs

permutation_iterator is a small, no_std Rust crate that lets you walk through a random permutation of the range [0, max) without ever building the permuted list in memory. Instead of the classic Fisher-Yates shuffle, which needs O(n) space to hold a copy of every element, it builds a Feistel network keyed by a random or caller-supplied 256-bit key and uses it as a pseudo-random permutation (PRP) over the input domain. Each call to next() runs the current counter through the network and discards outputs outside the requested range, giving O(1) space and amortized O(1) time per element.

The crate exposes Permutor for permutations of a single range and RandomPairPermutor for permutations over pairs drawn from two ranges (useful for iterating over the Cartesian product of two lists in random order without materializing it). Because the underlying Feistel network is a keyed bijection, the same key always reproduces the same permutation, which makes the crate useful anywhere you need a large space of unique, unguessable identifiers derived from a counter — the README’s own example is generating sequential-but-unpredictable credit card numbers without storing the full set already issued.

What You Get

• Permutor — an iterator over a random permutation of [0, max), constructible with a fresh random key (new), a caller-supplied u64 key, or a full 32-byte key for deterministic, reproducible permutations
• RandomPairPermutor — iterates over a random permutation of pairs (i, j) drawn from two ranges, without materializing the Cartesian product
• FeistelNetwork — the lower-level keyed pseudo-random permutation primitive, exposed publicly for callers who want to build custom permutation schemes on top of it
• Helper conversion functions (u128_to_16slice, u64_to_8slice, u64_to_32slice, integer_log2) for working with the fixed-width byte representations the network operates on
• no_std support, so the crate can run in embedded or WASM contexts (it depends on getrandom with the wasm-bindgen feature for entropy)

Common Use Cases

• Iterating over a large ID space (e.g. generating sequential-looking but unpredictable identifiers like credit card or coupon numbers) without storing already-issued values
• Shuffling huge or unbounded ranges where a Fisher-Yates shuffle’s O(n) memory footprint is impractical
• Producing a random but resumable/deterministic traversal order for property-based or fuzz testing, by fixing the 256-bit key
• Iterating over random pairs from two lists (e.g. random sampling of combinations) without allocating the full cross-product

Under The Hood

Architecture The crate is a single-module library (src/lib.rs) built around three cooperating types: FeistelNetwork, the core keyed pseudo-random permutation; Permutor, a thin iterator wrapper that drives the network across increasing inputs and filters outputs back into the requested [0, max) range; and RandomPairPermutor, which composes a Permutor over max1 * max2 and decodes each output into a coordinate pair. FeistelNetwork::new_with_slice_key rounds the requested max up to the next even power-of-two bit width, splits that width into left/right halves, and stores bitmasks used every round. permute() then runs a fixed 32-round Feistel construction, each round mixing the right half through a keyed hash (round_function, built on wyhash) and swapping halves — a textbook Feistel structure that turns a simple keyed hash into a full bijection over the padded domain. Because Permutor::next() discards outputs that land outside max, the effective cost per yielded value is the Feistel round count divided by the acceptance ratio, which the crate accepts as the tradeoff for O(1) space.

Tech Stack The crate targets Rust 2018 edition and is deliberately #![no_std], so it has no runtime allocator dependency. Its only non-dev dependencies are wyhash (a fast non-cryptographic hash used as the Feistel round function), getrandom (for gathering a random 256-bit key when the caller doesn’t supply one, with the wasm-bindgen feature enabled for browser/WASM targets), and anyhow (compiled with default-features = false for no_std-compatible error handling) used as the Result error type on the fallible constructors. Dev-dependencies add rand for the test suite’s randomness comparisons. CI (.travis.yml) runs cargo test --release, cargo fmt --check, cargo clippy -- -D warnings, and a cargo bench job on nightly, generated via a cargo-template-ci metadata block in Cargo.toml.

Code Quality The crate has real, if modest, test coverage: tests/feistel_network.rs and tests/permutor.rs cover boundary and correctness behavior of the two main types, and tests/randomness.rs runs a chi-squared comparison against a real Fisher-Yates shuffle to sanity-check output distribution — an unusually rigorous check for a small crate. src/lib.rs itself carries doctested examples on every public function (Permutor, RandomPairPermutor, and the byte-conversion helpers), which run as part of cargo test and double as living documentation. Error handling uses anyhow::Result on the fallible key-generation path rather than swallowing failures. The one visible rough edge: three fields on FeistelNetwork (half_width, right_mask, left_mask) are marked pub with a TODO visible just for testing, fix comment, meaning implementation details currently leak into the public API surface.

API Design The public surface is small and largely self-explanatory: Permutor::new(max) for the common case, with new_with_u64_key and new_with_slice_key variants for reproducible permutations, all returning a standard Iterator<Item = u128>. RandomPairPermutor::new(max1, max2) mirrors that pattern for pairs and yields (u64, u64). Both integrate directly with Rust’s for loops and iterator adapters with zero boilerplate beyond the constructor call, and the crate-level docs plus three runnable examples/ files (simple.rs, deterministic.rs, random_pair.rs) get a new user to working code in under a minute. The main friction point is the leaked pub internals on FeistelNetwork noted above, and the fact that u128/u64 types propagate through the API instead of being hidden behind newtypes.