Python reservoir sampling algorithm

gistfile1.py

from random import randrange

def reservoir_sampling(items, k):
    """ 
    Reservoir sampling algorithm for large sample space or unknow end list
    See <http://en.wikipedia.org/wiki/Reservoir_sampling> for detail>
    Type: ([a] * Int) -> [a]
    Prev constrain: k is positive and items at least of k items
    Post constrain: the length of return array is k
    """
    sample = items[0:k]

    for i in range(k, len(items)):
        j = randrange(1, i + 1)
        if j <= k:
            sample[j - 1] = items[i]

    return sample

• This code is wrong, even reservoir_sampling([1, 2, 3], k=1) will fail.
• If we know len(items) then this algorithm is not needed in the first place.

* This code is wrong, even `reservoir_sampling([1, 2, 3], k=1)` will fail.

* If we know `len(items)` then this algorithm is not needed in the first place.

@tommyod. Thanks for pointing out the problem, fix the bug. The idea of reservoir_sampling is that we don't know the length of the items or the items are too large to hold in memory. Yes, if the len(items) is know and can be hold in memory, the algorithm is useless.