Алгоритм: Какой самый быстрый способ проверить наличие набора?

Question

Имея массив из N наборов, какой самый быстрый способ создать график включения этих наборов?

Answer 1

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

Чтобы определить, является ли один набор X подмножеством Y, вам нужно выполнить | X | количество тестов членства на Y. занимает время, линейно пропорциональное | X |.

Итак, если у вас есть N наборов, и вы хотите выяснить, какие наборы являются подмножеством каких других наборов, вам придется выполнить N ² таких тестов подмножеств, поэтому я полагаю, что в итоге вы получите сложность O (AN ² ), где A - количество элементов в наибольшем наборе.

Даже если бы вы могли сделать что-то умное, чтобы решить «X подмножество Y» и «Y подмножество X» одновременно, вы бы не получили больше, чем коэффициент 2, поэтому сложность не улучшится.

Answer 2

Прежде всего, вы можете показать, что этот граф будет содержать O (n ^ 2) ребер при заданных n множествах: рассмотрим множества A1, ..., An с каждым Ak = {1, ..., k}. Тогда подмножество A1 A2, подмножество A1 A3, ..., подмножество A1 An, подмножество A2 A3, ..., что составляет n (n-1) / 2 ребер в графе включения.

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

Теперь для каждого элемента x разделите ваши множества на два: те, которые содержат x, и те, которые не содержат. Последнее может быть - подмножество первого. Добавьте соответствующие ребра в граф подмножества. Всякий раз, когда у нас есть пара вершин, соединенных в каждом направлении, мы знаем, что ни одна вершина не является подмножеством другой. Этот алгоритм O (mn ^ 2) для универсума из m элементов и n множеств.

эт вуаля!

Answer 3

Если у вас есть набор из N наборов, ни один из которых не содержит другого одинакового размера, вам нужно будет выполнить N ^ 2 сравнений наборов.

Answer 4

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

Использовать сортировку слиянием.

Ваш вывод представляет собой матрицу MxM включений (строка, столбец). Это инициализируется для всех ИСТИНА. Вот ваш алгоритм:

1. Если все наборы пусты, выйдите из
2. Взглянуть на первый элемент каждого непустого набора
3. Найдите минимум из них
4. Какой из просмотренных наборов содержит эти минимальные элементы?
5. Для наборов, определенных на шаге 4, набор включает (*, эти наборы) в ложное значение
6. Pop top элемент каждого набора, определенного на шаге 4
7. GOTO 0

Если все наборы пусты, у вас есть набор MxM