Feedback on Sets, and Partitions

[Anton Vredegoor]

David Eppstein <eppstein at ics.uci.edu> wrote:

>BTW, here is some code for generating these numbers.  I think it's a 
>little interesting that one can write the obvious one-line definition 
>for factorials, forgetting the base case, and then make it work anyway 
>via the magic of memoization.  Something to think about in connection 
>with PEP 318...

[snip some interesting code]

Here's a more tedious way to do the same, but this code is more
"graphic" in that it shows how one can build up a triangle of numbers
line by line according to some mutation prescription.

Depending on the kind of prescription one ends up with pascals
triangle or the triangle for bell numbers.

def pascal_mutate(L):
    R = [L[i] + L[i+1] for i in xrange(len(L)-1)]
    return [1] + R + [1]

def stirling_mutate(L):
    R = [L[i] + (i+2)*L[i+1] for i in xrange(len(L)-1)]
    return [1] + R + [1]

def triangle(mutator):
    L = [1]
    while 1:
        yield L
        L = mutator(L)

def listify(gen):
    cache = []
    def func(n):
        while len(cache) <= n:
            cache.append(gen.next())
        return cache[n]
    return func

def triangle_function_generator(mutator):
    T = listify(triangle(mutator))
    def func(n,k):
        return T(n)[k]
    return func

pascal = triangle_function_generator(pascal_mutate)
stirling_raw = triangle_function_generator(stirling_mutate)

def noverk(n,k):
    return reduce(lambda a,b: a*(n-b)/(b+1),range(k),1)

def stirling(n,k):
    return stirling_raw(n-1,k-1)

def bell(n):
    return sum([stirling(n,i) for i in range(1,n+1)])
    
def test():
    n,k = 10,4
    assert pascal(n,k) == noverk(n,k)
    print bell(25)

if __name__=='__main__':
    test()

#prints 4638590332229999353

Anton