Feedback on Sets, and Partitions

[David Eppstein]

In article <eppstein-A8F4BF.22001829042004 at news.service.uci.edu>,
 David Eppstein <eppstein at ics.uci.edu> wrote:

> In article <mailman.136.1083282936.25742.python-list at python.org>,
>  "Steve" <humean at fea.st> wrote:
> 
> > For my current project, I need to generate partitions of sets up to size
> > 25. I am rather hopeless it will ever be feasible, and I have begun
> > looking for a different approach. Thanks for any replies!
> 
> There are 4638590332229999353 partitions of an 25 item set.
> <http://www.research.att.com/projects/OEIS?Anum=A000110>
> 
> So, I think generating them all is a little out of the question.

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...


def memoize(recurrence, base_case={}):
    memo = {}
    for k,rk in base_case.items():
        if not isinstance(k,tuple):
            k = (k,)
        memo[k] = rk

    def memoized(*args):
        if args not in memo:
            memo[args] = recurrence(*args)
        return memo[args]

    return memoized

def factorial(n):
    return factorial(n-1)*n

factorial = memoize(factorial, base_case={0:1})

def choose(n,k):
    return factorial(n) // factorial(k) // factorial(n-k)

def bell(n):
    return sum([choose(n-1,k)*bell(n-1-k) for k in range(n)])

bell = memoize(bell, base_case={0:1})

print "There are",bell(25),"partitions of a 25 item set."

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science