3

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.

0fnt
  • 8,211
  • 9
  • 45
  • 62
  • PS I tried searching for a similar question, but couldn't find one. Please feel free to just link to the earlier question rather than answering this one if there is such a question. – 0fnt Apr 10 '11 at 18:41

3 Answers3

11

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.

Mat
  • 202,337
  • 40
  • 393
  • 406
0

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.

BMitch
  • 231,797
  • 42
  • 475
  • 450
  • This is answered all over the place, though most algorithms tend to go in reverse (last to first) so you simplify the calculation for the range of random numbers. http://www.codinghorror.com/blog/2007/12/shuffling.html, http://stackoverflow.com/questions/5383498/shuffle-rearrange-randomly-a-liststring – BMitch Apr 10 '11 at 18:47
  • What BMitch described, is called Knuth Shuffle. – Ankur Agarwal Sep 08 '12 at 23:16
  • @abc Knuth Shuffle is another name for the Fisher Yates shuffle according to that wikipedia link. – BMitch Sep 09 '12 at 00:02
0

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

Margus
  • 19,694
  • 14
  • 55
  • 103
  • In Mathematica function that does this, is called RandomSample. http://reference.wolfram.com/mathematica/ref/RandomSample.html – Margus Apr 10 '11 at 18:54