Choose M numbers from N with equal probability for all - PrismoSkills

Choose M numbers from N with equal probability for all - PrismoSkills

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-P₁)*(1/N)

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

= (N-1)/ N²


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 3^rd element becomes:

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

= 1/N

Read full article from Choose M numbers from N with equal probability for all - PrismoSkills