algorithm - 如何快速生成随机排列

Question

我在一本算法书上看到一道题:

"Given a positive integer n, choose 100 random permutations of [1,2,...,n],..."

我知道如何使用 Knuth 算法生成随机排列。但是是否存在生成大量排列的快速算法？

Answer 1

Knuth 洗牌要求您对 n 个元素的排列进行 n 次随机交换(请参阅 http://en.wikipedia.org/wiki/Random_permutation#Knuth_shuffles )，因此复杂度为 O(n)，如果您收到 n 个元素的排列，这大约是您可以预期的最好结果。

这会给您带来实际问题吗？如果是这样，也许你可以看看你在实践中对所有这些排列所做的事情。除了简单地靠更少的钱过活之外，您还可以考虑推迟生成排列，直到您确定需要它为止。如果您需要对 n 个对象进行排列，但只查看这 n 个对象中的 k 个，那么您可能需要一种仅生成这 k 个元素的方案。对于较小的 k，您可以简单地随机生成 [0, n) 范围内的 k 个随机数，重复生成返回已经出现的数字。对于较小的 k，这不太可能。