Алгоритм объединения наборов, состоящих как минимум из двух общих элементов

Question

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

• С_1:[ 1, 2, 3, 4 ]
• С_2:[ 3, 4, 5, 6, 7 ]
• С_3 :[ 8, 9, 10, 11 ]
• С_4:[ 1, 8, 12, 13 ]
• С_5 :[ 6, 7, 14, 15, 16, 17 ]

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

• [ 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 N).Отнеситесь к этому с недоверием.

Answer 2

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

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

Answer 3

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

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

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

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

Павел.

Answer 4

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

Answer 5

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

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