permutation-iterator

一个 Rust 库，用于遍历随机排列，而不将其完全加载到内存中。

permutation-iterator 允许您遍历一个随机排列，例如随机顺序的值 [0, 1, 2, 3, 4, 5]。它使用常量空间；它不会在内存中完全实例化这些值然后进行洗牌。

用法

将以下内容添加到您的 Cargo.toml

[dependencies]
permutation_iterator = "0.1.2"

示例

随机，单个整数范围

以下是如何遍历范围 [0, max)（即 0 包含到 max 不包含）中的随机排列整数的方法。每次运行此操作时，您都会得到不同的排列。

use permutation_iterator::Permutor;

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

确定性，单个整数范围

您还可以传递一个 key 以遍历一个确定性随机排列。每次运行此操作时，您都会得到相同的排列。

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);
    }
}

随机，整数对

如果您有两个整数向量，并且想要遍历这些列表的随机排列对，可以使用

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]);
    }
}

实现细节

生成随机排列的一种方法是对列表进行洗牌。例如，给定输入整数 [0, 1, 2, 3, 4, 5]，可以将其洗牌，例如到 [5, 3, 2, 0, 1, 4]。每个输入元素映射到一个唯一的输出元素，反之亦然（每个输出元素映射到一个唯一的输入元素）。当你从左到右消费洗牌后的列表时，你正在消费这个随机排列。

使用Fisher-Yates算法，洗牌的时间复杂度为O(n)，但是它也具有O(n)的空间复杂度。我们需要在内存中保留元素的副本以便进行洗牌。如果输入范围很大，或者你运行的环境内存受限，这会很不方便。

密码学提供了一个替代方案。对称加密可以归结为将给定的输入映射到唯一的输出，映射是通过一个单独的秘密密钥改变的，反之亦然（每个输出元素映射到一个唯一的输入元素）。如果这种双射映射不存在，我们就无法可靠地恢复原始输入。一种具体的对称加密方法使用的是块密码（每次操作n位）和通过Feistel网络实现的。

Feistel网络是一个非凡的结构，它允许你重复使用简单、相对较弱的不可逆函数，并将其转化为复杂、相对较强的可逆排列。因此，在常数时间内，我们可以通过迭代随机排列来加密输入。我们可以类似地通过恢复排列来解密输出。

考虑一个银行的例子，该银行试图生成唯一的信用卡号码。实际的信用卡号码需要非常安全地存储，我们不愿意为了找到下一个可用的号码而查阅它们。通过仅存储密钥和最后生成的信用卡号码，我们可以安全且高效地继续迭代所有信用卡号码的随机排列，而不会出现重复。

许可证

permutation-iterator在Apache许可证（版本2.0）的条款下分发。有关详细信息，请参阅许可证。