#python #set
Вопрос:
У меня есть куча предметов, которые были отсортированы по разным наборам. Эти наборы могут не иметь нулевого пересечения между ними. Как я могу найти все наборы, которые не содержатся ни в одном из существующих наборов?
Например:
- пункты: a,b,c,d
- наборы: {a,b,c}, {a, b}, {a}, {a,b,c,d}, {b,d,c}
В этом случае результат должен быть: {a}, {b,d,c}
- {a,b,c,d} содержит {a,b,c} содержит {a, b} содержит {a}
- {a,b,c,d} содержит {b,d,c}
Мой подход состоял бы в том, чтобы создать график с:
- узлы — это наборы
- существует разница между набором 1 и набором 2, если набор 1 содержится в наборе 2
Как только я построю график, решением будут ребра без предшественников (или входящих ребер).
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 nlt;m]) print([n for n, in_degree in G.in_degree() if in_degree == 0]) Комментарии:
1. Я в замешательстве. Если вы пытаетесь найти наборы, не содержащиеся в других наборах, почему решением будет {a} и {b,c,d}?
2. Вызов add_edges_from, похоже, занимает квадратичное время, верно? В этом случае ваш метод не кажется лучше, чем тест подмножества грубой силы, подобный этому
[set_ for set_ in allsets if not any(otherset.issubset(set_) for otherset in allsets if otherset is not set_)]
Ответ №1:
Вот два других способа без networkx :
sorted_sets = sorted(sets, key=len, reverse=True) minimal = [] while sorted_sets: s = sorted_sets.pop() for m in minimal: if m lt;= s: break else: minimal.append(s) или
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 lt;= s: break elif s lt; m: remove.add(m) else: minimal.add(s) minimal -= remove Вывод для
sets = [{"a", "b", "c"}, {"a", "b"}, {"a"}, {"a", "b", "c", "d"}, {"b", "d", "c"}] является
[{'a'}, {'c', 'd', 'b'}] {frozenset({'a'}), frozenset({'c', 'd', 'b'})}