Алгоритм объединения наборов, которые имеют как минимум 2 элемента

Question

Дан список наборов:

• S_1: [1, 2, 3, 4]
• S_2: [3, 4, 5, 6, 7]
• S_3: [8, 9, 10, 11]
• S_4: [1, 8, 12, 13]
• S_5: [6, 7, 14, 15, 16, 17]

Какой самый эффективный способ объединить все наборы, которые имеют как минимум 2 элемента? Я полагаю, это похоже на проблему со связанными компонентами. Таким образом, результат будет:

• [1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 UNION S_2 UNION S_5)
• [8, 9, 10, 11]
• [1, 8, 12, 13] (S_4 делит 1 с S_1 и 8 с S_3, но не объединяет, поскольку они имеют только один элемент в каждом)

Наивной реализацией является O (N ^ 2), где N - количество наборов, которое для нас неработоспособно. Это должно быть эффективно для миллионов наборов.

Answer 1

Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

Моя голова говорит, что это про Орден (2N LN). Возьми это с крошкой соли.

Answer 2

Если вы можете заказать элементы в наборе, вы можете посмотреть, используя Mergesort на наборах. Единственная необходимая модификация - это проверка на наличие дубликатов на этапе объединения. Если он найден, просто откажитесь от дубликата. Поскольку сортировка слиянием равна O (n * log (n)), это обеспечит улучшенную скорость по сравнению с алгоритмом наивного O (n ^ 2).

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

Answer 3

Я не понимаю, как это можно сделать менее чем за 0 (n ^ 2).

Каждый набор должен сравниваться с любым другим, чтобы увидеть, содержат ли они 2 или более общих элемента. Это n * (n-1) / 2 сравнений, поэтому O (n ^ 2), даже если проверка общих элементов занимает постоянное время.

В сортировке наивной реализацией является O (n ^ 2), но вы можете воспользоваться транзитивным характером упорядоченного сравнения (так, например, вы не знаете, что в нижнем разделе быстрой сортировки нужно сравнивать с чем-либо в верхний раздел, так как он уже сравнивался с осью). Вот что приводит к сортировке O (n * log n).

Это не применимо здесь. Поэтому, если в наборах нет чего-то особенного, что позволяет нам пропускать сравнения, основанные на результатах предыдущих сравнений, в общем случае это будет O (n ^ 2).

Paul.

Answer 4

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

Answer 5

Если ваши элементы имеют числовой характер или могут быть упорядочены естественным образом (т. Е. Вы можете присвоить значение, такое как 1, 2, 42 и т. Д.), Я бы предложил использовать сортировку по осям на слитых наборах, и сделать второй проход, чтобы подобрать уникальные элементы.

Этот алгоритм должен иметь значение O (n), и вы можете оптимизировать радикальную сортировку с помощью операторов побитового сдвига и битовых масок. Я сделал нечто подобное для проекта, над которым работал, и он работает как шарм.