Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Choose M numbers from N with equal probability for all

Puzzle: How do you pick M numbers from an array of N integers such that probability of choosing each one of them is the same?

Solution: Let us choose just one number first.

Probability of the first number being picked up is 1/N

If we follow the same approach for the next number, then its probability of being chosen is:

= (1-P1)*(1/N)

= (1-1/N)*(1/N)

= (N-1)/ N2

This is not what we want.
To choose the second element with same probability, we can do the following:
1. Swap the first chosen element with the last element of the array.

2. Choose a random element from the remaining N-1 elements.

With this approach, the probability of second element becomes:

= (N-1)/N * 1/(N-1)

= 1/N

Similarly, probability for 3rd element becomes:

= (N-1)/N * (N-2)/(N-1) * 1/(N-2)

= 1/N

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: