[SciPy-user] combinatorics - all set partitions

alex argriffi@ncsu....
Tue Oct 28 14:57:40 CDT 2008


Marek Wojciechowski wrote:
> 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!
>   
You might want to call it something other than partition to avoid 
conflicts with the builtin function.


More information about the SciPy-user mailing list