algorithm - 生成前 n 个自然数的随机排列的最有效方法是什么？

Question

到目前为止，我一直在使用一个列表来跟踪遇到的所有唯一数字。我正在使用随机数生成器来获取 1 和 n 之间的随机数。如果该数字已经在我的列表中，那么我将继续生成随机数，直到遇到不在列表中的数字。当我得到一个不在我的列表中的新号码时，我将它添加到我的列表中并重复该过程，直到所有“n”个号码都在我的列表中。

显然这种方法效率很低。有人可以为此提出一个有效的解决方案吗？

Answer 1

Knuth 是你的人选，尽管还有其他算法可用。

Answer 2

• 用从 1 到 N 的数字创建一个有序列表。
• 随机播放它（即，创建它的排列）。这可以在线性时间内完成（参见这个算法）。