无限洗牌

一个组合数学库。

一个重要功能是能够指定一个大组合空间，然后以随机顺序遍历它，永远不会重复同一个状态，而且 无需 在内存中生成和存储整个状态空间。我们通过，本质上，将状态空间视为一种数系，然后使用一个 对称密码 PCG 线性反馈移位寄存器，以随机顺序迭代每个元素的索引来实现。

use mako_infinite_shuffle::{light_shuffle, Cross, Indexing};
fn main(){
    let d = light_shuffle(Cross(0..3, 0..2));
    for i in 0..d.len() {
        println!("{:?}", d.get(i));
    }
}

(2, 1)
(1, 0)
(2, 0)
(0, 1)
(0, 0)
(1, 1)

基本功能正常，但由于许多原因，库尚未完成

• 在我编写代码后不久，我就意识到它在可能的所有维度上都非常不实用。

  • 如果状态空间如此之大，为什么需要采取特殊步骤来保证非碰撞？（我们已假设128位哈希ID的非碰撞性）

  • 如果你真的需要一个绝对保证（而不是概率保证），无论你有什么形而上学的理由，为什么不只是记录你已生成的项目，并跳过之前已经出现过的项目呢？

  • 这对于连续空间不起作用，因此我认为它不适用于加权抽样，这基本上是你想要做的所有类型的procgen或抽样的基础。我们生活在一个模拟世界中（或者至少我们生活在一个我们无法不将其建模为模拟来理解世界的复杂性水平上）

• 在不到两小时的时间里，我找不到一个能够产生非常非常小的密文（例如，16位或更少。即使是字节大小的也非常粗糙，因为这可能迫使我们不得不在单次迭代中重新运行加密100次。这不是致命的，但非常糟糕）的对称块密码。

• 它不会是一个非常好的API，因为Rust缺少可变参数泛型。目前，所有东西都只是对配对有效，这是可行的，但它会产生难以管理的类型列表结构。

我保留它来记录这个概念，以防万一出现某种奇怪的情况，它最终还是有意义的。

我不确定这个想法是从哪里来的，但这篇文章也讨论了它。据说有一些实现。

我检查了crypto_secretbox，fpe和cloudproof_fpe。所有这些都对允许的位数字符串长度设定了下限。只有8的下限是可以接受的，但cloudproof_fpe的下限是20。

对于非加密选项（更快，易于适应小尺寸），LCG或PCG会很好，但我目前正使用LFSR。