Алгоритм поиска общих подмножеств

У меня есть N количество наборов S i чисел, каждый разного размера. Пусть m 1 , m 2 , ... m n - размеры соответствующих наборов ( m i = | S i | ), а M - размер наибольшего набора. Мне нужно найти общие подмножества, в которых есть как минимум два числа. Пример:

Set  Items
1    10,80,22
2    72, 10, 80, 26,50
3    80,
4    10, 22
5    22, 72, 10, 80, 26,50

Итак, результат будет таким

Items                Found in sets
10, 22               1, 4
10, 80               1, 2, 5
10, 80, 22           1, 5
10, 72, 80, 26, 50   2, 5

Итак, как автоматизировать эту проблему и какова ожидаемая сложность для соответствующего решения? Мне нужно, чтобы это было как можно быстрее.

6
задан outis 15 October 2010 в 21:26
поделиться