模拟数组的随机迭代

Question

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

我知道 you can't have full randomness without storing full array，但我不需要真正随机的顺序。我需要它被用户认为是随机的。该解决方案应使用次线性 space.

一个可能的建议——使用大质数——是given here。这个解决方案的问题是有一个明显的固定步骤（采用模块数组大小）。我更喜欢一个不是那么明显非随机的解决方案。有更好的解决方案吗？

Answer 1

也许你可以使用这个：http://www.cplusplus.com/reference/algorithm/random_shuffle/ ?

Answer 2

正如其他人所指出的，您可以通过随机排列数组索引然后跟随它来预先创建一种 "flight plan" 。这违反了 "it will be best if current state can be stored in a few integers" 约束，但这真的重要吗？ 是否有严格的性能限制？毕竟，我相信如果您不接受重复，那么您需要将您已经访问过的项目存储在某个地方或以某种方式。

或者，您可以选择 侵入式 解决方案并在数组的每个元素中存储一个 bool ，告诉您该元素是否已被选中。这可以通过使用继承（根据需要使用多个）以几乎干净的方式完成。
这个解决方案带来了许多问题，例如线程安全，当然违反了"keep the array intact"约束。

Answer 3

您提到的二次留数 ("using a large prime") 是众所周知的，可以工作，并且保证每个元素都恰好迭代一次（如果需要，但似乎并非严格如此？ ).不幸的是，它们不是 "very random looking"，除了必须是素数才能工作之外，对模还有一些其他要求。
Jeff Preshing 的网站上有一个页面详细描述了该技术并建议 feed the output of the residue generator into the generator again with a fixed offset。

但是，既然你说你只需要 "perceived as random by user"，那么你似乎可以用连续的整数来提供哈希函数（比如 cityhash 或 siphash）。输出将是一个 "random" 整数，并且 至少到目前为止 会有一个严格的 1:1 映射（因为可能的哈希值比那里多得多是输入）。

现在的问题是你的数组很可能没有那么大，所以你需要以某种方式减少这些生成的索引的范围而不生成重复项（很难）。

显而易见的解决方案（取模）不会起作用，因为它几乎可以保证您得到很多重复项。

使用位掩码将范围限制为 2 的下一个更大的幂应该可以工作而不会引入偏差，丢弃超出范围的索引（生成新索引）也应该可以工作。请注意，这需要不确定的时间——但这两者的组合平均来说应该工作得相当好（最多尝试几次）。

否则，"really works" 唯一的解决方案是改组索引数组，正如 Kamil Kilolajczyk 所指出的（尽管您不希望那样）。

Answer 4

如果你能得到一个你可以控制最大周期的随机生成器，那么模拟随机播放的随机生成器的想法是好的。

A Linear Congruential Generator 用公式计算一个随机数：

x[i + 1] = (a * x[i] + c) % m;

最大周期为 m 并且在以下属性成立时实现：

参数c和m互质。
对于每个素数r除以m,a - 1是以下的倍数r。
如果m是4的倍数那么a - 1也是4的倍数.

我的第一个 darft 涉及使 m 成为数组长度后 4 的下一个倍数，然后找到合适的 a 和 c 值。这是 (a) 大量工作和 (b) 有时会产生非常明显的结果。

我重新考虑了这种方法。我们可以使 m 成为数组长度适合的最小二乘方。 m 的唯一质因数是 2，这将使每个奇数都与它互质。除了 1 和 2，m 将被 4 整除，这意味着我们必须使 a - 1 是 4 的倍数。

m 大于数组长度意味着我们必须丢弃所有非法数组索引值。这最多每隔一回合发生一次，应该可以忽略不计。

以下代码生成周期为 m 的伪随机数。我已经避免了 a 和 c 的微不足道的值，并且在我的（不是太多）现场检查中，结果看起来还不错。至少没有明显的循环模式。

所以：

class RandomIndexer
{
public:
    RandomIndexer(size_t length) : len(length)
    {
        m = 8;
        while (m < length) m <<= 1;

        c = m / 6 + uniform(5 * m / 6);
        c |= 1;

        a = m / 12 * uniform(m / 6);
        a = 4*a + 1;
        x = uniform(m);                      
    }

    size_t next()
    {
        do { x = (a*x + c) % m; } while (x >= len);

        return x;
    }

private:
    static size_t uniform(size_t m)
    {
        double p = std::rand() / (1.0 + RAND_MAX);

        return static_cast<int>(m * p);
    }

    size_t len;
    size_t x;
    size_t a;
    size_t c;
    size_t m;
};

然后您可以像这样使用生成器：

std::vector<int> list;
for (size_t i = 0; i < 3; i++) list.push_back(i);

RandomIndexer ix(list.size());
for (size_t i = 0; i < list.size(); i++) {
    std::cout << list[ix.next()]<< std::endl;
}

我知道这仍然不是一个很好的随机数生成器，但它相当快，不需要数组的副本并且似乎工作正常。

如果随机选择 a 和 c 的方法产生不好的结果，最好将生成器限制在某些2 的幂并硬编码已被证明是好的文献值。

Answer 5

这个算法怎么样？

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

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

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

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

Answer 6

这是一个 java 解决方案，它可以很容易地转换为 C++ 并且类似于上面 M Oehm 的解决方案，尽管选择 LCG 参数的方式不同。

import java.util.Enumeration;
import java.util.Random;

public class RandomPermuteIterator implements Enumeration<Long> {
    int c = 1013904223, a = 1664525;
    long seed, N, m, next;
    boolean hasNext = true;

    public RandomPermuteIterator(long N) throws Exception {
        if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N);
        this.N = N;
        m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)));
        next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE));
    }

    public static void main(String[] args) throws Exception {
        RandomPermuteIterator r = new RandomPermuteIterator(100);
        while (r.hasMoreElements()) System.out.print(r.nextElement() + " ");
        //output:50 52 3 6 45 40 26 49 92 11 80 2 4 19 86 61 65 44 27 62 5 32 82 9 84 35 38 77 72 7 ...
    }

    @Override
    public boolean hasMoreElements() {
        return hasNext;
    }

    @Override
    public Long nextElement() {
        next = (a * next + c) % m;
        while (next >= N) next = (a * next + c) % m;
        if (next == seed) hasNext = false;
        return  next;
    }
}

模拟数组的随机迭代

Simulate random iteration of array

c++

arrays

random

algorithm