Identifying non-intersecting (super-)sets

I would turn this from a set problem into a graph problem by constructing a graph whose nodes are the graphs with edges connecting sets with an intersection.

Here is some code that does it. It takes a dictionary mapping the name of the set to the set. It returns an array of sets of set names that connect.

def set_supersets (sets_by_label):
    element_mappings = {}
    for label, this_set in sets_by_label.items():
        for elt in this_set:
            if elt not in element_mappings:
                element_mappings[elt] = set()
            element_mappings[elt].add(label)
    graph_conn = {}
    for elt, sets in element_mappings.items():
        for s in sets:
            if s not in graph_conn:
                graph_conn[s] = set()
            for t in sets:
                if t != s:
                    graph_conn[s].add(t)

    seen = set()
    answer = []
    for s, sets in graph_conn.items():
        if s not in seen:
            todo = [s]
            this_group = set()
            while 0 < len(todo):
                t = todo.pop()
                if t not in seen:
                    this_group.add(t)
                    seen.add(t)
                    for u in graph_conn[t]:
                        todo.append(u)
            answer.append(this_group)
    return answer

print(set_supersets({
    "A": set([1, 2]),
    "B": set([1, 3]),
    "C": set([4, 5]),
    "D": set([3, 6])
}))

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top