сопоставление с образцом

Question

Предположим, у меня есть такой набор кортежей (каждый кортеж будет иметь 1,2 или 3 элемента):

Мастер-набор:

 {(A) (A,C) (B,C,E)}

и, предположим, у меня есть другой наборкортежи, подобные этому:

Реальный набор: {(BOB) (TOM) (ERIC,SALLY,CHARLIE) (TOM,SALLY) (DANNY) (DANNY,TOM) (SALLY) (SALLY,TOM,ERIC) (BOB,SALLY) }

Что я хочу сделать, это извлечь все подмножества кортежей из реального набора, где элементы кортежей можно заменить, чтобы они стали такими же, какмастер-набор.

В приведенном выше примере будут возвращены два набора:

{(BOB) (BOB,SALLY) (ERIC,SALLY,CHARLIE)}

(пусть BOB = A, ERIC = B, SALLY = C, CHARLIE = E)

и

{(DANNY) (DANNY,TOM) (SALLY,TOM,ERIC)}

(пусть DANNY = A, SALLY = B, TOM = C, ERIC = E)

Это своего рода сопоставление с образцом, я полагаю, что-то вроде комбинаторики.Я действительно не знаю, как классифицировать эту проблему и какие у нее общие планы атаки.Что бы посоветовали эксперты по переполнению стека?

Answer 1

Разделите ваши кортежи по размерам.В каждом наборе создайте структуру данных, которая позволяет эффективно запрашивать кортежи, содержащие данный элемент.Первая часть этой структуры - ваши кортежи в виде массива (так что каждый кортеж имеет канонический индекс).Второй набор: Map String (Set Int).Это несколько занимает много места, но, надеюсь, не запрещает.

Тогда , вы, по сути, грубая сила.Для всех назначений первого основного набора ограничьте все назначения другими основными наборами.Для всех оставшихся назначений для второго, ограничьте все назначения для третьего и выше и т. Д. Алгоритм в основном индуктивный.

Я должен добавить, что я не думаю, что проблема является NP-полной, а простоплоская экспоненциальная наихудшая ситуация.Это не проблема решения, а проблема перечисления.И довольно легко представить сценарии входов, которые взрываются в геометрической прогрессии.

Answer 2

Это будет трудно сделать эффективно, поскольку ваша задача, вероятно, NP-полна (она включает изоморфизм подграфа в качестве особого случая).Тем не менее, предполагается, что шаблоны и база данных различаются по размеру.Сколько данных вы ищете?Насколько сложными будут ваши шаблоны?Сначала я бы порекомендовал решение для грубой силы, а затем проверил, не слишком ли это медленно, и вам нужно что-то более оригинальное.