In the programming pearls book by Jon Bentley, there is a section about the problem of finding a random set of m integers from range 0 to n-1 integers. To do so they use Knuth's algorithm given by the following code (see also here). How can I proof that this code indeed chooses every set of m integers from the range 0 to n-1 with equal probability.
def select_random(n, m):
to_pick = n
remaining = m
positions = []
for position in range(n):
big_int = generate_random_big_int()
if big_int % remaining < to_pick:
position.append(position)
to_pick --
remaining--
return positions
Aucun commentaire:
Enregistrer un commentaire