algorithm - 查找之前是否出现过随机数

Question

首先让我明确一点，这是一个人为的例子，而不是现实世界中的问题。

如果我在创建 0 到 10 之间的随机数时遇到问题。我会这样做 11 次，以确保不会再次绘制之前出现的数字，如果我得到重复的数字，我再次创建另一个随机数，以确保它之前没有被看到。所以基本上我得到了一个随机顺序从 0 - 10 的唯一数字序列例如3 1 2 0 5 9 4 8 10 6 7 等等

现在想出逻辑来确保随机数是唯一的而不是我们之前绘制的，我们可以使用多种方法

使用 C++ std::bitset并设置索引对应的位等于每个随机数的值。下次抽取新的随机数时检查。

或者

使用 std::map<int,int>计算次数甚至简单的 C 数组，其中存储一些标记值以指示该数字是否发生。

如果我必须避免上述这些方法，并使用一些数学/逻辑/位运算来查找之前是否绘制过随机数，有没有办法？

Answer 1

你不想按照你建议的方式去做。考虑当您已经选择了 11 项中的 10 项时会发生什么；您的随机数生成器将循环直到找到丢失的数字，这可能永远不会，具体取决于您的随机数生成器。

更好的解决方案是创建一个按顺序排列的数字 0 到 10 的列表，然后将列表打乱为随机顺序。执行此操作的常规算法归功于 Knuth、Fisher 和 Yates:从第一个元素开始，将每个元素与位置大于数组中当前元素的元素交换。

function shuffle(a, n)
    for i from n-1 to 1 step -1
        j = randint(i)
        swap(a[i], a[j])

我们假设一个索引为 0 到 n-1 的数组，以及一个将 j 设置为范围 0 <= j <= i 的 randint 函数。