洗牌数组元素/ N号均匀随机。 Possibley预期O（n）的时间 [英] Shuffle elements of an array/n numbers uniformly randomly. Possibley in expected O(n) time

问题描述

是否有可能重新洗牌的n大小的数组元素的统一，即所有的n的概率！组合发生的是一样的，预计 O（N）的时间。怎么会这样？ 我要洗牌 A 的元素到一个新的数组 B 浮现在我的脑海里，当我试图做这只是选择一个随机数我从1到n的第一件事，看看 A [我] 已被摘下来，如果是这样，然后重复，否则就把 A [1] 中的第一个可用的位置 B 。 不过，此优惠券收集问题预计时间为O（n log n）的。 有人建议可以在 O（N）预计时间的算法。

Is it possible to shuffle elements of an n-sized array uniformly, i.e. the probability of any of the n! combinations occurring is the same, in expected O(n) time. How so? I have to shuffle elements of A to a new array B The first thing that comes to my mind when I'm trying to do this is just picking a random number i from 1 to n, see if A[i] has already been picked, if so, then repeat, otherwise put A[i] in the first available position in B. However, this coupon collector problem has expected time O(n log n). Can someone suggest an O(n) expected time algorithm.

感谢。

推荐答案

您应该看看渔民耶茨洗牌。

从文章：

执行得当，费雪耶茨   洗牌是公正的，让每一位   置换同样是可能的。该   现代版的算法是   相当有效，只需要还   时间成比例的数   项目被打乱并没有额外的   存储空间。

Properly implemented, the Fisher–Yates shuffle is unbiased, so that every permutation is equally likely. The modern version of the algorithm is also rather efficient, requiring only time proportional to the number of items being shuffled and no additional storage space.

所以，满足您的需求。这是pretty的容易实现了。

So it meets your requirements. It's pretty easy to implement too.

这篇关于洗牌数组元素/ N号均匀随机。 Possibley预期O（n）的时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！