随机地对数组的元素/n个数进行打乱。可能在预期的O(n)时间内

Question

是否有可能均匀地对n大小的数组中的元素进行洗牌，即n！在预期的O(n)时间内，出现的组合是相同的。怎么会这样呢？当我尝试这样做的时候，我想到的第一件事就是从1到n中挑选一个随机数i，看看A[i]是否已经被选中了，如果已经被选中了，那么重复一遍，否则就把A[i]放在B中第一个可用的位置。然而，此优惠券收集器问题已预期时间O(n log n)。有人能推荐一个O(n)预期时间算法吗？

谢谢。

Answer 1

你应该看看Fisher-Yates混洗。

摘自文章：

正确实现了，费舍尔-叶茨混洗是无偏见的，因此每个排列的可能性都是相等的。现代版本的算法也相当有效，只需要与被混洗的项目数量成比例的时间，而不需要额外的存储空间。

所以它能满足你的需求。它也很容易实现。

Answer 2

对于每个数组位置：

从当前位置到数组末尾选择一个随机数

将当前位置与随机位置交换

这应该会给你O(n)，而不需要寻找一个未使用的数组位置。这假设您可以使用就地交换，并且不必创建新的数组。

Answer 3

您需要的是set的 ，它以相等的概率对每个元素进行采样。