Search code examples
pythonrecursionset

How to recursively join subsets into a list in python?

I have a list of sets:

my_set = [[1, 2, 3], [1, 5], [4, 5, 6], [7, 8]]

I want to join all subsets that have elements in common (at least with one subset) in this list, into a single subset:

my_final_set = [[1, 2, 3, 4, 5, 6], [7, 8]]

In this case, the the elements 1, 2, 3, 4, 5, 6 must be grouped in a single final subset, as the image shows. How can I do it in Python? image

I think I should do some recursive approach, but I couldn't think of a way to do it.

Solution

  • You can take two sets and reduce it:

    
def get_union(sets):
    def _rec(S, B):
        A = set(S)
        i = 0
        while i < len(B):
            if A.intersection(B[i]):
                A.update(B.pop(i))
                A, B = _rec(A, B)
            else:
                i += 1
        return A, B

    res = []
    while sets:
        C, sets = _rec(sets[0], sets[1:])
        res.append(list(C))
    return res


print(get_union([[1, 2, 3], [1, 5], [4, 5, 6], [7, 8]]))

    Prints

    [[1, 2, 3, 4, 5, 6], [8, 7]]