algorithm - 在没有数组的情况下迭代打乱 [0..n)

Question

我知道一些例程如下:

X_n+1 = Routine(X_n, max)

例如，LCG 生成器之类的东西:

X_n+1 = (a*X_n + c) mod m

此生成器中没有足够的参数化来生成每个序列。

梦想功能:

X_n+1 = Routine(X_n, max, permutation number)

此例程由所有排列集合中的索引参数化，将返回序列中的下一个数字。序列可能是任意大的(因此存储数组和使用因数是不切实际的。

如果做不到这一点，是否有人有指向类似函数的指针，这些函数要么是无状态的，要么对于任意“最大值”具有恒定数量的状态，以便它们将迭代一个随机列表。

Answer 1

有n! n 个元素的排列。存储您使用的是哪一个至少需要 log(n!)/log(2) 位。根据斯特林的近似值，这大约需要 n log(n)/log (2) 位。

显式存储一个索引需要 log(n)/log(2) 位。存储所有 n，就像在索引数组中一样，需要 n 倍的次数，或者再次是 n log(n)/log(2)。从信息理论上讲，没有比显式存储排列更好的方法了。

换句话说，你传入的你想要的集合中什么排列的索引与写出排列占用相同的渐近存储空间。例如，如果将排列的索引限制为 32 位值，则最多只能处理 12 个元素的排列。 64 位索引最多只能给你 20 个元素。

由于索引占用与排列相同的空间，因此要么将您的表示更改为直接使用排列，要么接受解包为大小为 N 的数组。