Shuffle array elements / n evenly evenly. Possibly in expected time O (n)
Is it possible to uniformly move the elements of an n-size array, i.e. the probability of any of n! the combinations occur the same at the expected time O(n)
. How so? I have to shuffle the elements A
into a new array B
The first thing that comes to my mind when I try to do this is just pick a random number i
from 1 to n, see if it A[i]
has already been selected, if so, then repeat, otherwise put A[i]
in the first available position in B
. However, this issue with the coupon collector was waiting for a while O(n log n)
. Can anyone suggest an algorithm for the expected time O(n)
.
Thank.
source to share
You should look at Fisher-Yates in random order.
From the article:
Correctly implemented, the Fischer-Yates reshuffle is unbiased so that each reshuffle is equally likely. The modern version of the algorithm is also quite efficient, requiring proportional quantities of items to be shuffled and no additional storage space is added.
Thus, it suits your requirements. It's also pretty easy to implement.
source to share
For each position in the array:
Select a random number from the current position to the end of the array
Swap current position with random position
This should give you O (n) no problem of finding the position of an unused array. This assumes that you can use in-place exchange and that you do not need to create a new array.
source to share
You want a random sample from a set that displays each item with equal probability.
source to share