How to find all the smallest sets not contained in any other set

user_12388365 0
Viewed 66

I have a bunch of items which have been sorted in different sets. These sets might have not null intersection between them. How can I find all the sets that are not contained in any of the existing sets?

For example:

  • items: a,b,c,d

  • sets: {a,b,c}, {a, b}, {a}, {a,b,c,d}, {b,d,c}

In this case the result should be: {a}, {b,d,c}

  • {a,b,c,d} contains {a,b,c} contains {a, b} contains {a}

  • {a,b,c,d} contains {b,d,c}

My approach would be to create a graph with:

  • nodes are the sets
  • there is an edege between set 1 and set 2 if set 1 is contained in set 2

Once I build the graph the solution will be the edges without predecessors (or incoming edges).

G=nx.DiGraph()

G.add_nodes_from([frozenset({'a', 'b', 'c'}),frozenset({'a', 'b'}), frozenset({'a'}), frozenset({'a', 'b', 'c', 'd'}), frozenset({'b', 'd', 'c'})])

G.add_edges_from([(n, m) for n in G for m in G if n!=m if n<m])

print([n for n, in_degree in G.in_degree() if in_degree == 0])
set python
1 Answers

Here are two other ways without networkx:

sorted_sets = sorted(sets, key=len, reverse=True)
minimal = []
while sorted_sets:
    s = sorted_sets.pop()
    for m in minimal:
        if m <= s:
            break
    else:
        minimal.append(s)

or

frozen_sets = {frozenset(s) for s in sets}
minimal= set()
while frozen_sets:
    s = frozen_sets.pop()
    remove = set()
    for m in minimal:
        if m <= s:
            break
        elif s < m:
            remove.add(m)
    else:
        minimal.add(s)
        minimal -= remove

Output for

sets = [{"a", "b", "c"}, {"a", "b"}, {"a"}, {"a", "b", "c", "d"}, {"b", "d", "c"}]

is

[{'a'}, {'c', 'd', 'b'}]

{frozenset({'a'}), frozenset({'c', 'd', 'b'})}
user_143112630
Related