reservoir sampling

'''
Problem: You will get a stream of numbers and your job is to pick an element randomly from 1 to i where i is the current elment.

so at the ith timestamp, you have to choose a number from 1 to i given probability of getting choosen of all numbers should be same.
so if you put the random number in [1,i], the probability of getting i to be chosen is same as other numbers ie. 1/i so for every i, get a random number out of [1,i] and if number=i else let the result be previous number.
'''
import random

def reservoir_sampling(stream):
    result = None
    i = 0

    for val in stream:
        i += 1

        # pick current element with probability 1/i
        if random.randint(1, i) == i:
            result = val
        # else: keep previous result

    return result

for i in range(100):
    print(reservoir_sampling([i for i in range(100)]),end=' ')