How to find all partitions of a set

user_52041 0
Viewed 24271

I have a set of distinct values. I am looking for a way to generate all partitions of this set, i.e. all possible ways of dividing the set into subsets.

For instance, the set {1, 2, 3} has the following partitions:

{ {1}, {2}, {3} },
{ {1, 2}, {3} },
{ {1, 3}, {2} },
{ {1}, {2, 3} },
{ {1, 2, 3} }.

As these are sets in the mathematical sense, order is irrelevant. For instance, {1, 2}, {3} is the same as {3}, {2, 1} and should not be a separate result.

A thorough definition of set partitions can be found on Wikipedia.

partitioning set algorithm c#
8 Answers
def allPossiblePartitions(l): # l is the list whose possible partitions have to be found


    # to get all possible partitions, we consider the binary values from 0 to 2**len(l))//2-1
    """
    {123}       --> 000 (0)
    {12} {3}    --> 001 (1)
    {1} {2} {3} --> 010 (2)
    {1} {23}    --> 011 (3)  --> (0 to (2**3//2)-1)

    iterate over each possible partitions, 
    if there are partitions>=days and
    if that particular partition contains
    more than one element then take max of all elements under that partition
    ex: if the partition is {1} {23} then we take 1+3
    """
    for i in range(0,(2**len(l))//2):
            s = bin(i).replace('0b',"")
            s = '0'*(len(l)-len(s)) + s
            sublist = []
            prev = s[0]
            partitions = []
            k = 0
            for i in s:
                if (i == prev):
                    partitions.append(l[k])
                    k+=1
                else:
                    sublist.append(partitions)
                    partitions = [l[k]]
                    k+=1
                    prev = i
            sublist.append(partitions)
            print(sublist)
user_130525790
Related