创建无重复的随机数序列

Question

重复:

O(1)中的唯一随机数？

我想要一个伪随机数生成器,它可以按随机顺序生成没有重复的数字.

例如:

随机(10)

可能会返回5,9,1,4,2,8,3,7,6,10

有没有更好的方法来做到这一点,除了使数字的范围和洗牌,或检查生成的列表重复？

---

编辑:

此外,我希望它在没有整个范围的情况下有效地生成大数字.

---

编辑:

我看到每个人都建议使用随机算法.但是,如果我想生成大的随机数(1024字节+),那么该方法将占用更多的内存,而不是我刚使用常规RNG并插入到Set中,直到它是指定的长度,对吧？对此没有更好的数学算法.

Answer 1

您可能对线性反馈移位寄存器感兴趣.我们曾经用硬件来构建它们,但我也用软件完成了它们.它使用移位寄存器,其中一些位被xor'ed并反馈到输入,如果你选择正确的"抽头",你可以得到一个与寄存器大小一样长的序列.也就是说,一个16位的lfsr可以生成一个长度为65535且没有重复的序列.它在统计上是随机的,但当然是非常可重复的.此外,如果它做错了,你可以得到一些令人尴尬的短序列.如果你查看lfsr,你会发现如何正确构造它们的例子(也就是说,"最大长度").

Answer 2

shuffle是一种非常好的方法(如果你没有使用朴素算法引入偏差).见Fisher-Yates shuffle.

Answer 3

为了确保列表不重复,它必须保留先前返回的数字列表.因为它必须在算法结束时生成整个列表,这相当于生成有序列表然后混洗的存储要求.

关于改组的更多信息:从有序列表中创建随机有序列表

但是,如果随机数的范围非常大但所需的数量很少(您已经暗示这是评论中的实际要求),那么生成一个完整的列表并将其洗牌是浪费的.大型阵列上的随机播放涉及以某种方式访问​​虚拟内存页面(根据定义)将破坏操作系统的寻呼系统(在较小规模上,CPU的内存缓存会出现同样的问题).

在这种情况下,搜索列表到目前为止将更加有效.因此,理想的做法是使用启发式(由实验确定)为给定的参数选择正确的实现.(在C#而不是C++中给出示例的道歉但ASFAC++ B我正在训练自己在C#中思考).

IEnumerable<int> GenerateRandomNumbers(int range, int quantity)
{
    int[] a = new int[quantity];

    if (range < Threshold)
    {
        for (int n = 0; n < range; n++)
            a[n] = n;

        Shuffle(a);
    }
    else
    {
        HashSet<int> used = new HashSet<int>();

        for (int n = 0; n < quantity; n++)
        {
            int r = Random(range);

             while (!used.Add(r))
                 r = Random(range);

             a[n] = r;
        }
    }

    return a;
}

检查重复数字的成本,有碰撞时的循环等将是昂贵的,但是可能会有一些Threshold值,它变得比分配整个范围更快.

对于足够小的数量要求,使用数组used并在其中进行线性搜索可能更快,因为更大的局部性,更低的开销,比较的便宜......

同样对于大量和大范围,可能最好在请求时返回在序列中产生数字的对象,而不是预先为结果分配数组.由于yield return关键字,这在C#中很容易实现:

IEnumerable<int> ForLargeQuantityAndRange(int quantity, int range)
{
    for (int n = 0; n < quantity; n++)
    {
        int r = Random(range);

        while (!used.Add(r))
            r = Random(range);

        yield return r;
    }
}

Answer 4

如果保证随机数不再重复,则它不再是随机的,随机数随着数字的产生random(10)而减少(九个数字相当可预测之后,即使只有八个数字,你有50%的机会).

Answer 5

我了解您不希望大范围洗牌，因为您必须存储整个列表才能这样做。

而是使用可逆的伪随机哈希。然后依次输入值0 1 2 3 4 5 6等。

这样的哈希数是无限的。如果将它们限制为2的幂，则生成它们并不难，但是可以使用任何基数。

例如，如果您想遍历所有2 ^ 32 32位值，则可以使用这种方法。这是最简单的编写方法，因为在这种情况下，整数数学的隐式mod 2 ^ 32会对您有所帮助。

unsigned int reversableHash(unsigned int x)
{
   x*=0xDEADBEEF;
   x=x^(x>>17);
   x*=0x01234567;
   x+=0x88776655;
   x=x^(x>>4);
   x=x^(x>>9);
   x*=0x91827363;
   x=x^(x>>7);
   x=x^(x>>11);
   x=x^(x>>20);
   x*=0x77773333;
   return x;
}