模拟数组的随机迭代

Question

我有一个给定大小的数组.我想以伪随机顺序遍历它,保持数组完整并访问每个元素一次.如果当前状态可以存储在几个整数中,那将是最好的.

我知道你不能在没有存储完整数组的情况下完全随机,但我不需要命令是非常随机的.我需要它被用户视为随机的.解决方案应该使用子线性空间.

这里给出了一个可能的建议 - 使用大素数.该解决方案的问题在于存在明显的固定步骤(采用模块阵列大小).我更喜欢一种不是非随机的解决方案.有更好的解决方案吗？

Answer 1

这个算法怎么样？

来伪伪随机遍历一个大小为n的数组。

1. 创建一个大小为 k 的小数组
2. 使用大素数方法填充小数组，i = 0
3. 使用 RNG 从小数组中随机删除一个位置，i += 1
4. 如果 i < n - k 则使用大素数方法添加新位置
5. 如果 i < n 转到 3。

k 越高，获得的随机性就越大。这种方法将允许您延迟从素数方法生成数字。

通过创建另一个数组“skip-list”，可以采用类似的方法来生成比序列中预期更早的数字。随机选择序列中稍后的项目，使用它们遍历下一个位置，然后将它们添加到跳过列表中。当它们自然到达时，将在跳跃列表中搜索它们并进行抑制，然后从跳跃列表中删除，此时您可以随机将另一个项目添加到跳跃列表中。