Everyday-is-a-birthday Problem

In [1]:

    

# A decorator that memoize functions
def dynamic_programme(_F):
    cache = {}

    def memoizedF(*args):
        if args not in cache:
            cache[args] = _F(*args)
        return cache[args]
    
    dynamic_programme.cache = cache
    return memoizedF

def fac_ratio(n): # n:int, returns n!/(n^n)
    _r = 1
    for i in range(n, 0, -1):
        _r *= i/n
    return _r

# Probability of n items to fully fill m spots
@dynamic_programme
def fill_spots(n, m): # n, m : int, n >= m   
    if m == 1:
        return 1
    elif n == m:
        return fac_ratio(n)
    else:
        # If we already know n-1 item's spot, the last item has 
        #    two possible way to satisfy the all-filled condition:
        #  1. the spots are already filled by n-1 items
        #  2. there is only one spot left and the last item fills it
        _all_filled = fill_spots(n-1, m)
        _one_left = 1/m * (fill_spots(n-1, m-1) - _all_filled)
        _prob = _one_left + _all_filled
        return _prob


    

In [5]:

    

import matplotlib.pyplot as plt
%matplotlib inline
import seaborn as sns

import sys
sys.setrecursionlimit(10000)
#print(fac_ratio(200))
k = []
for i in range(366, 7000):
    k.append(fill_spots(i, 365))

plt.plot(range(366, 7000), k)
print(max(k))


    

    




7.997389623915987e-143