c - 如何在 C 中生成长(最多 2500 万)整数随机序列(不重复)？

Question

我需要生成长(伪)随机数组(1000-25 000 000 个整数)，其中没有重复的元素。从rand()开始我该怎么做函数生成的数字不够长？

我尝试使用这个想法:array[i] = (rand() << 14) | rand() % length;不过我想还有更好的方法，但我不知道。

感谢您的帮助。

Answer 1

您可以使用Fisher-Yates shuffle为此。

创建一个由 n 个元素组成的数组，并按顺序填充每个元素。

-------------------------
| 1 | 2 | 3 | 4 | 5 | 6 |
-------------------------

在此示例中，n 为 6。现在选择一个从 0 到 n-1 的随机索引(即 rand() % n)并交换该索引处的数字与数组顶部的数字。假设随机索引为 2。因此我们交换索引 2 (3) 处的值和 n-1 (6) 处的值。现在我们有:

                      v
-------------------------
| 1 | 2 | 6 | 4 | 5 | 3 |
-------------------------

现在我们做同样的事情，这次索引的上限是 n-2。然后我们将该索引处的值与索引 n-2 处的值交换。假设我们随机得到 0。因此我们将索引 0 (1) 与索引 n-2 (5) 交换:

                  v
-------------------------
| 5 | 2 | 6 | 4 | 1 | 3 |
-------------------------

然后重复。假设下一个随机索引是 3。这恰好是我们的上限，所以没有变化:

              v
-------------------------
| 5 | 2 | 6 | 4 | 1 | 3 |
-------------------------

接下来我们得到 0:

          v
-------------------------
| 6 | 2 | 5 | 4 | 1 | 3 |
-------------------------

最后1:

      v
-------------------------
| 6 | 2 | 5 | 4 | 1 | 3 |
-------------------------