Select a random element from a stream with uniform probability (we only have access to the current element, and a function to get the next element which returns EOF when at the end of the stream).

reservoir_sampling.py

import random

def uniform_random_from_stream(stream):
	""" Returns a random number from an enumerable with uniform probability
	by using a "reservoir sampling" algorithm """
	
	reservoir = []
	sample_count = 1
	for index, item in enumerate(stream):
		if index < sample_count:
			reservoir.append(item)
		else:
			r = random.randint(0, index)
			if r < sample_count:
				reservoir[r] = item
			
	return reservoir[0]