Big Lehmer

Big Lehmer is a lib for converting between arbitrarily sized sequence permutations into compact Lehmer codes and back to their uncompressed representation.

The number sequence must have similar properties as [0.N].shuffle. Basically sequential numbers in random order, starting at zero. The lib technically supports up to u32::MAX numbers, but performance will be the main issue beforehand.

Usage

fn main() {
    let sequence = [7, 2, 0, 6, 5, 1, 4, 3];
    let lehmer_code = big_lehmer::encode(&sequence).unwrap();
    let mut roundtrip = [0; 8];
    big_lehmer::decode(&lehmer_code, &mut roundtrip).unwrap();
    assert_eq!(sequence, roundtrip);
}

Benchmarks:

Measured on my "old system" (i7- 6700k). Not very accurate, just to showcase performance expectations.

The crate is mainly optimized for large sequences.

Performance for large sequences is dominated by the big integer math. A possible optimization is to replace Dashu with rug. Apparently rug (=GMP) is extremely well optimized, but it's not native rust and not trivial to get working.