[SciPy-user] combinatorics - all set partitions

Marek Wojciechowski mwojc@p.lodz...
Tue Oct 28 14:11:22 CDT 2008


Marek Wojciechowski wrote:

> Hi!
> I'm trying to find an algorithm (and possibly the python code)
> implementing the problem of finding all possible partitions of the set.
> 
> Example of all partitions for the set { 1, 2, 3 } is:
> { {1}, {2}, {3} }
> { {1, 2}, {3} }
> { {1, 3}, {2} }
> { {1}, {2, 3} }
> { {1, 2, 3} }
> but i need general partitioning tool.
> 
> I thought maybe someone from the group knows the solution...
> 
> Greetings,

Thanks for the answers.. However I've ended up finally with writing the
generator by myself:

from copy import deepcopy
def addelement(partlist, e):
    newpartlist = []
    for part in partlist:
        npart = part + [[e]]
        newpartlist += [npart]
        for i in xrange(len(part)):
            npart = deepcopy(part)
            npart[i] += [e]
            newpartlist += [npart]
    return newpartlist

def partition(n):
    if n == 0: return []
    partlist = [[[1]]]
    for i in xrange(2, n+1):
        partlist = addelement(partlist, i)
    return partlist

print partition(4) 

This seems to give good results and is enough for me. 

Thanks again!
-- 
Marek Wojciechowski



More information about the SciPy-user mailing list