Lehmer
Lehmer is a Rust crate for converting between permutation vectors, Lehmer codes and their decimal representations. It is designed to run as quickly as possible and as a result, doesn't do any error handling.
This implementation is based on the 'Mapping Permutations to Integers' section of this paper. It doesn't implement the linear time speedup as the speed gains are only ~10% and require precomputing a lookup table.
Usage
extern crate lehmer;
use Lehmer;
Lehmer supports permutations up to 20 elements in length. The behaviour is not specified for permutations longer than this and will likely cause a panic. No unsafe operations are used, though.
Additionally, permutations must be vectors containing sequential integers
starting from 0 (in any order), e.g. [1, 0, 4, 3, 2]
. Lehmer will either
panic
or produce incorrect results for other vectors.
Benchmarks
Benchmarks can be run with cargo bench
:
test benchmark_from_decimal ... bench: 264 ns/iter (+/- 10)
test benchmark_from_permutation ... bench: 83 ns/iter (+/- 9)
test benchmark_max_value ... bench: 13 ns/iter (+/- 1)
test benchmark_to_decimal ... bench: 40 ns/iter (+/- 2)
test benchmark_to_permutation ... bench: 142 ns/iter (+/- 9)
e.g. Lehmer::from_permutation
runs at ~13 million iterations per second.
Tests
Tests can be run with cargo test
. Unit tests are in files next to their
modules and integration tests are in tests/
.
Contributions
Contributions are welcome. Please test/benchmark your changes and open a PR.