Найти количество пар непересекающихся множеств в списке множеств

Question

Задача состоит в следующем: по заданному списку из n множеств, каждое из которых содержит k целых чисел, найти количество пар непересекающихся множеств.Предположим, что возможные элементы множеств положительны и ограничены сверху c> n, и предположим, что k << n.</p>

Я пытаюсь придумать эффективный алгоритм, чтобы решить это быстрее, чем O (kn ^ 2), который является временем выполнения наивного решения.

Лучшая стратегия, которую я мог придумать, включает в себя итерацию каждого набора в списке и хэширование элементов набора, так что каждый элемент в наборе сопоставляется с набором индексов наборов, которые содержатЭто.Затем для текущего набора в итерации используйте его элементы c в качестве ключей и рассмотрите объединение наборов индексов c, которые заданы в качестве значений в хеш-таблице.Этот результирующий набор индексов представляет количество наборов, встречающихся таким образом, если они не пересекаются с текущим набором, который мы можем использовать, чтобы найти количество непересекающихся наборов.Суммирование этого значения на протяжении всей итерации дает правильный ответ.Однако, поскольку операция объединения является O (n), эта стратегия работает не лучше, чем простое решение.

Какое наиболее эффективное возможное решение этой проблемы?

Answer 1

При k << n вы можете уменьшить сложность на: </p>

• Сортировка каждого набора, который может быть в n * k * log (k)
• Затем сортировка всехустанавливает по первому последнему элементу n * log (n)

Теперь для сравнения нужно выполнить n * (n - 1) операций, которые:

• Любое сравнение s1.Lastв s2.First (что должно быть в большинстве случаев, так как k << n) </li>
• Или эффективно искать пересечение s1 s2, которое является максимальным по k, учитывая, что s1 и s2 отсортированы