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

Question

У меня есть N количество наборов S _i чисел, каждый из которых имеет свой размер. Пусть m ₁ , m ₂ , ... m _n будет размеры соответствующих наборов ( m _i = | S _i | ) и M - размер наибольшего набора. Я должен найти общие подмножества, которые имеют по крайней мере два числа в них. Пример: * 1 027 *

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

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

Answer 1

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

Сначала обсудите, является ли выход экспоненциальным по отношению к вашему входу. Предположим, у вас есть 2 элемента и N наборов. Предположим, что каждый элемент принадлежит каждому набору; это потребует N строк в качестве ввода. Тогда сколько строк вы должны напечатать?

Я думаю, что вы собираетесь напечатать 2 ^N -N-1 строк, например:

1,2     1,2
1,2     1,3
.....
1,2     1,N
1,2     2,1
.....
1,2     1,2,3
.....
1,2     1,2,3,...N

Поскольку вы потратите O (2 ^N ) времени на печать, вы можете выбрать любое из предложений на этой странице, чтобы рассчитать эту информацию - вы все равно были пойманы экспонентом. 1012 *

Этот аргумент сделает ваше обсуждение очень быстрым.

Answer 2

Вас просят сделать попарное пересечение всего вашего набора, а затем собрать все результаты размером> = 2.

Есть O (N ^ 2) пар.Делать пересечение O (M) для каждого.Соберите все результаты, отсортируйте их по заданному содержимому, чтобы обработать дубликаты: N ^ 2 Log N ^ 2 (в худшем случае пересечение различно для каждой пары, поэтому может быть O (N ^ 2) наборов результатов)

Так что я думаю, что сложность O ((N ^ 2 + N log N) * M)

Но где-то вполне возможна ошибка.

Пол

Answer 3

Вы можете сделать это -

1. Создать хеш-таблицу и вставить в качестве ключей каждый ваш элемент и значения в качестве наборов, к которым он принадлежит. Eg: 10:[0,1,3,4] 80:[0,1,2,4] 22:[0,3,4] 72:[1,4] 26:[1,4] 50:[1,4]

2. После этого для каждых 2 элементов в хэш-таблице найдите пересечение значений ключей.Здесь пересечение (10, 80) дает [0,3,4].Сделайте это для (10,22) (10,72) ... У вас есть свой результат.

3. Сложность - Чтобы вставить M элементов в Хэш-таблицу - O (M) Поиск каждоговведите в хеш-таблицу - O (1) Операция пересечения значений ключа - O (m ^ 2) [Это можно оптимизировать]

В целом я бы сказал, что это O (м ^ 2) Алго.Но если размер «Предметов» невелик в каждом «наборе», вы не заметите большого снижения производительности.

Answer 4

Одно решение, которое я могу придумать:

Используйте хеш-таблицу, сгенерируйте всю комбинацию «пары чисел» из чисел в этой «строке», что составляет O (M * M) времени.

Затем используйте их в качестве хеш-ключей, сопоставляя их с индексом основного массива.

For each row of those N elements,
  do the step above... and if the hash already maps to a number, then it is a match,
    then return the pair, or else just put those in the hash

это О (Н * М * М)

обновление: , если, как вы говорите в комментарии, M может быть максимум 15, тогда O (N * M * M) в действительности совпадает с O (N).

---

Если ваш первоначальный вопрос - найти все пары, то

For each row of those N elements,
  do the step first mentioned... and if the hash already maps to a number, 
    then it is a match and just print out the pair if this pair is not printed yet
  and in any event, put the mapping into the hash

to tell whether a pair has been printed, created another hash, such as
  printed_or_not[i,j] = true or false, 
    and make sure to check printed_or_not[i,j] or printed_or_not[j, i]
    because not need to print again if just different order

Answer 5

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