Подход, предложенный PengOne, будет работать, но он не очень эффективен.Чтобы понять, почему это не помогает, рассмотрим следующий патологический пример:
Предположим, у вас есть юниверс U, в котором есть n различных элементов, и пусть набор всех искомых наборов состоит из всех подмножеств U сровно k элементов.Тогда верно, что ни одна пара множеств здесь не содержится строго друг в друге;и поэтому в худшем случае вам придется искать по всем n выбрать k возможных наборов!Другими словами, использование предложенной им структуры данных ничуть не лучше наивного линейного поиска в худшем случае.
Очевидно, что вы можете добиться гораздо большего, чем это, и правильная структура данных для использования была бы бесполезной: http://en.wikipedia.org/wiki/Trie
Чтобы приспособить три для работы с наборами вместо просто строк, достаточно установить порядок элементов универсального набора, а затем закодировать каждое из ваших подмножеств в виде двоичной строки конечной длины,где i-й символ равен 0 или 1 в зависимости от того, содержит ли набор i-й элемент.Вот реализация на python
import math
class SetTree:
def __init__(self, index, key, left, right):
self.index = index
self.key = key
self.left = left
self.right = right
cached_trees = { }
cached_index = 2
def get_index(T):
if isinstance(T, SetTree):
return T.index
if T:
return 1
return 0
def make_set_tree(key, left, right):
global cached_trees, cached_index
code = (key, get_index(left), get_index(right))
if not code in cached_trees:
cached_trees[code] = SetTree(cached_index, key, left, right)
cached_index += 1
return cached_trees[code]
def compute_freqs(X):
freqs, total = {}, 0
for S in X:
for a in S:
if a in freqs:
freqs[a] += 1
else:
freqs[a] = 1
total += 1
U = [ (-f, a) for a,f in freqs.items() ]
U.sort()
return U
#Constructs the tree recursively
def build_tree_rec(X, U):
if len(X) == 0:
return False
if len(U) == 0:
return True
key = U[0][1]
left_elems = [ S for S in X if key in S]
if len(left_elems) > 0:
return make_set_tree(key,
build_tree_rec(left_elems, U[1:]),
build_tree_rec([ S for S in X if not key in S ], U[1:]))
return build_tree_rec(X, U[1:])
#Build a search tree recursively
def build_tree(X):
U = compute_freqs(X)
return build_tree_rec(X, U)
#Query a set tree to find all subsets contained in a given set
def query_tree(T, S):
if not isinstance(T, SetTree):
return [ [] ] if T else []
if T.key in S:
return [ U + [ T.key ] for U in query_tree(T.left, S) ] + query_tree(T.right, S)
return query_tree(T.right, S)
#Debugging function: Converts a tree to a tuple for printing
def tree_to_tuple(T):
if isinstance(T, SetTree):
return (T.key, tree_to_tuple(T.left), tree_to_tuple(T.right))
return T
Теперь вот пример использования:
In [15]: search_tree = set_search.build_tree(set_family)
In [16]: set_search.tree_to_tuple(search_tree)
Out[16]:
(2,
(4, (5, True, True), (5, True, (3, True, False))),
(4, (5, True, False), (1, True, False)))
In [17]: set_search.query_tree(search_tree, set([2,3,4,5]))
Out[17]: [[5, 4, 2], [4, 2], [5, 2], [3, 2], [5, 4]]
In [18]: set_search.query_tree(search_tree, set([1,2,3,4,5]))
Out[18]: [[5, 4, 2], [4, 2], [5, 2], [3, 2], [5, 4], [1]]
In [19]: set_search.query_tree(search_tree, set([2,4,5]))
Out[19]: [[5, 4, 2], [4, 2], [5, 2], [5, 4]]
In [20]: set_search.query_tree(search_tree, set([2,5]))
Out[20]: [[5, 2]]
In [21]: set_search.query_tree(search_tree, set([1]))
Out[21]: [[1]]
In [22]: set_search.query_tree(search_tree, set([15]))
Out[22]: []
Обратите внимание, что объем работы, выполняемой query_tree, пропорционален размеру поддерева, которое представляетнабор всех результатов, возвращаемых query_tree.Таким образом, наша цель состоит в том, чтобы вычислить размер одной из подпунктов (в среднем), а затем в качестве вторичной цели минимизировать это количество.Один из способов сделать это - переупорядочить элементы универсального в терминах нисходящей частоты, чтобы они повторялись как можно меньше раз на нижних уровнях дерева.Эта оптимизация также выполняется в приведенном выше коде.Вторичной оптимизацией является кэширование деревьев, которые уже были найдены, чтобы избежать необходимости переделывать ненужную работу.
РЕДАКТИРОВАТЬ: Сразу после того, как я закончил набирать это, я увидел ответ btilly, который приходит более или менеетот же вывод о проблеме (по модулю некоторых технических прыщей, которые я переместил в комментарии к его сообщению.)
РЕДАКТИРОВАТЬ 2: Понял, что это действительно просто частный случай бинарной диаграммы решений.На самом деле не хватает энергии, чтобы исправить ситуацию прямо сейчас, поэтому оставлю все как есть.Возможно, исправим это завтра.http://en.wikipedia.org/wiki/Binary_decision_diagram