## Choose M numbers from N with equal probability for all: How do you pick M numbers from an array of N integers such that probability
of choosing each one of them is the same?Puzzle: Let us choose just one number first.SolutionProbability 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-P _{1})*(1/N)= (1-1/N)*(1/N) = (N-1)/ N ^{2}This is not what we want. To choose the second element with same probability, we can do the following: - Swap the first chosen element with the last element of the array.
- 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 3 ^{rd} element becomes:= (N-1)/N * (N-2)/(N-1) * 1/(N-2) = 1/N |

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: |

Facebook comments:

Site Owner: Sachin Goyal