创建无重复的随机数序列

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

1> gbarry..：

---

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

---

LFSR是一种非常有效且简单的解决方案 - 但您必须选择合适的常量才能使它们正常工作.网上有资源可以帮助解决这个问题.

---

您最好不要尝试构建RNG frmo scratch.太多可能会出错.如果你已经有一个像样的RNG你可以使用(在Boost左右),你应该使用它.几乎所有的周期=模数的方法都会产生许多非重复的数字,但这对你来说似乎毫无用处

2> Mitch Wheat..：

---

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

3> Daniel Earwi..：

---

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

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

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

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

IEnumerable 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 used = new HashSet();

        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 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;
    }
}

---

第一句话不是真的.正确设置线性反馈移位寄存器的实现将在其返回开始之前精确地遍历其范围内的所有值.

4> Motti..：

---

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

5> SPWorley..：

---

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

而是使用可逆的伪随机哈希。然后依次输入值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;
}