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

Question

到现在为止，我一直在使用一个列表来跟踪所有遇到的唯一数字。我正在使用一个随机数生成器来获得1到n之间的随机数。如果这个数字已经在我的列表中，那么我只是继续生成随机数字，直到我遇到一个不在我列表中的数字。当我收到一个不在我的名单上的新号码时，我将它添加到我的名单中，并重复该过程，直到列表中出现所有'n'号码。

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

Answer 1

Knuth's your man为此，虽然其他算法可用。

Answer 2

• 从1创建与数字的有序列表，以N.
• 随机播放它（即，创建它的置换）。这可以通过线性时间完成（参见this algorithm）。