Lib.rs

Lehmer

Lehmer 是一个 Rust crate，用于在排列向量、Lehmer 码及其小数表示之间进行转换。它设计得尽可能快，因此不进行任何错误处理。

此实现基于该文档的“将排列映射到整数”部分：此论文。它没有实现线性时间加速，因为速度提升仅为约10%，并且需要预计算查找表。

用法

extern crate lehmer;

use lehmer::Lehmer;

fn main() {
    // Compute the Lehmer code for a permutation:
    let lehmer = Lehmer::from_permutation(&[1, 0, 4, 3, 2]);

    assert_eq!(vec![1, 0, 2, 1, 0], lehmer.code);
    assert_eq!(29, lehmer.to_decimal());

    // Compute the Lehmer code for a decimal (requires the permutation length)
    let another = Lehmer::from_decimal(29, 5);

    assert_eq!(vec![1, 0, 2, 1, 0], another.code);
    assert_eq!(vec![1, 0, 4, 3, 2], another.to_permutation());

    // Compute the maximum decimal value for a permutation of five elements
    let max = Lehmer::max_value(5);
    assert_eq!(119, max);
}

Lehmer 支持20个元素长度的排列。对于超过此长度的排列，行为未指定，可能会引发恐慌。不过，不使用任何不安全操作。

此外，排列必须是包含从0开始的连续整数的向量（顺序不限），例如 [1, 0, 4, 3, 2]。Lehmer 对于其他向量要么引发 panic，要么产生不正确的结果。

基准测试

可以使用 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)

例如，Lehmer::from_permutation 的运行速度约为每秒1300万次迭代。

测试

可以使用 cargo test 运行测试。单元测试位于其模块旁边的文件中，集成测试位于 tests/。

贡献

欢迎贡献。请测试/基准测试您的更改并提交 PR。