combination.py

gistfile1.txt

def c(n, r):
    print n, r
    if r == 1: return n
    if n == r: return 1

    return c(n-1, r) + c(n-1, r-1)

# can compute it on time
print c(5, 2)

# cannot finish it ontime
# or stack will overflow
c(999, 33)


# use cache to speed up

cache = {}
def c1(n, r):
    if r == 1: return n
    if n == r: return 1

    if (n,r) in cache:
        return cache[(n,r)]

    v = c1(n-1, r) + c1(n-1, r-1)
    cache[(n,r)] = v
    return v

print c1(999, 33)