[SciPy-user] combinatorics - all set partitions
Marek Wojciechowski
mwojc at p.lodz.pl
Tue Oct 28 15:11:22 EDT 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