lundi 15 août 2016

How to proof Knuth's algorithm S correct

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