Shuffle elements of an array/n numbers uniformly randomly. Possibley in expected O(n) time

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.

Thanks.

You should look at the Fisher-Yates shuffle.

From the article:

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.

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

For each array position:

Select a random number from current position to end of array

Swap current position with random position

That should give you O(n) without the challenge of finding an unused array position. This assumes you can use an in-place swap and that you don't have to create a new array.

What you want is random sample of set, that samples each element with equal probability.