rs.py

from itertools import tee
from random import randrange

num_random_bits = 0

def random_bit():
    global num_random_bits
    num_random_bits += 1
    return randrange(2)

def split(xs):
    xs1, xs2 = tee(xs)
    return (x for b, x in xs1 if b == 0), (x for b, x in xs2 if b == 1)

STOP = object()

def random_permutation(xs):
    xs1, xs2 = tee(xs)
    x = next(xs2, STOP)
    if x is STOP:
        return
    if next(xs2, STOP) is STOP:
        yield x
        return
    xs1, xs2 = split((random_bit(), x) for x in xs1)
    yield from random_permutation(xs1)
    yield from random_permutation(xs2)

def random_sample(xs):
    return next(random_permutation(xs))

n = 1000
num_tests = 1000

# num_events = 0
# histogram = {}
# for i in range(num_tests):
#     x = random_sample(range(n))
#     histogram[x] = histogram.get(x, 0) + 1

# print(1/n)
# for x in sorted(histogram):
#     print(x, "=>", histogram[x]/num_tests)

histogram = {}
for i in range(num_tests):
    num_random_bits = 0
    random_sample(range(n))
    histogram[num_random_bits] = histogram.get(num_random_bits, 0) + 1

print(sorted(((v, k) for k, v in histogram.items()), reverse=True))