Алгоритм слияния множеств, в которых используется не менее двух элементов

Учитывая список наборов:

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]

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

[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 - количество множеств, что для нас невозможно. Это должно быть эффективным для миллионов наборов.

Ответ 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). Возьмите это с солью.

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

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

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

Павел.

Ответ 5

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

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