from random import *            # library for simulating random numbers
from pylab import *             # library for making plots

# the probability of not having two people with the same birthday for 0 to n people
def birthday_prob(n):
    days = 365
    B = [0]*(n+1)
    B[0] = 1.0
    r = days
    for i in range(1, n+1):
        B[i] = B[i - 1] * r / days
        r = r - 1
    return B

# plot the probability of two people having the same birthday for up to 80 people
def plot_birthday_prob():
    plot(range(81), map(lambda p: 1 - p, birthday_prob(80)), 'x')
    ylim([0.0, 1.0])            # sets the boundary values of the y axis
    show()                      # displays the plot


# perform a simulation of the birthday experiment for n people t times
# output a vector indicating the times event E_n occurred
def simulate_birthdays(n, t):
    days = 365
    occurred = []
    for time in range(t):
        # choose random birthdays for everyone
        birthdays = []
        for i in range(n):
            birthdays.append(randint(1, days))
        # record the occurrence of event E_n
        occurred.append(same_birthday(birthdays))
    return occurred

# check if event E_n occurs (two people have the same birthday)
def same_birthday(birthdays):
    for i in range(len(birthdays)):
        for j in range(i):
            if birthdays[i] == birthdays[j]:
                return True
    return False

# for a sequence of event occurrences over time,
# calculate the fraction of times the event has occurred so far
def frac_occur(events):
    so_far = 0
    frac_times = []
    for i in range(len(events)):
        so_far = so_far + events[i]
        frac_times.append(so_far * 1.0 / (i + 1))
    return frac_times

# plot the fraction of times two people have the same birthday in a group of 23
# in up to 1000 simulations of the birthday experiment
def plot_simulate_birthdays():
    plot(range(1000), frac_occur(simulate_birthdays(23, 1000)))
    ylim([0.0, 1.0])            # sets the boundary values of the y axis
    show()                      # displays the plot