Максимальное пересечение между n наборами

У меня есть x наборов с y элементами (unsorted integers) в каждом из них. Я хочу найти максимальный размер пересечения между парой этих множеств.

Например:

* 5 наборов, размер = 3

установить 1:1 2 3

установить 2: 4 2 3

установить 3: 5 6 7

установить 4: 5 8 9

установить 5: 5 10 11

максимальное пересечение установило 1 с множеством 2, а размер 2; ответ 2.

Итак, я могу сделать это в O (x ^ 2 * y), используя HashSets, просто глядя на все пары и вычисляя их размер пересечения. Но я хочу сделать это быстрее. Я думаю, что есть определенный алгоритм или структура данных, которые могут помочь. Можете ли вы дать мне какую-то идею?

UPDATE: x и y составляет около 10 ^ 3, элементы - int. И нет равных множеств.

Ответы

Ответ 1

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

Как вы можете его использовать:

Если у вас есть наборы A, B, C длины n и

intersection(A,B) = p
intersection(A,C) = q

затем

intersection(B,C) <= n - abs(p - q)

Для наборов в вашем случае:

S0 = { 1 2 3 }
S1 = { 4 2 3 }
S2 = { 5 6 7 }

вы вычисляете intersection(S0,S1) = 2 и запоминаете результат:

[ i(0,1)=2 ]

то intersection(S0,S2) = 0, поэтому

[ i(0,1)=2; i(0,2)=0 ]

И когда вы вычисляете intersection(S1,S2) после сравнения первых элементов

(S1[0]=4 != S2[0]=5)

вы можете сказать, что intersection(S1,S2) <= 2 - лучший результат, который у вас есть.

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

Я не уверен, что это лучший вариант. Возможно, существует совершенно другой подход к этому.

Ответ 2

Вот несколько psuedocode:

function max_intersection(vector<vector<int>> sets):
    hashmap<int, vector<set_id>> val_map;
    foreach set_id:set in sets:
        foreach val in set:
            val_map[val].push_back(set_id);
    max_count = 0
    vector<int> counts = vector<int>(size = sets.size() * sets.size(), init_value = 0);
    foreach val:set_ids in val_map:
        foreach id_1:set_id_1 in set_ids:
            foreach id_2:set_id_2 in set_ids where id_2 > id_1:
                count = ++counts[set_id_1 * sets.size() + set_id_2];
                if (count > max_count):
                    max_count = count;
    return max_count;

Итак, если X - количество множеств, а Y - количество элементов в каждом наборе:

  • Вставка в val_map равна O(X*Y)
  • Создание counts и инициализация каждого элемента до нуля - O(X^2)
  • Если нет пересечений (каждое значение происходит ровно один раз), последний цикл выполняется во времени O(X*Y). Однако, с другой стороны, если существует большое количество пересечений (все множества эквивалентны), то последний цикл выполняется в O(X^2*Y).

Таким образом, в зависимости от количества пересечений временная сложность находится где-то между O(X*Y + X^2) и O(X^2*Y).

Ответ 3

Я не могу придумать решение, которое улучшит O(x*x*y), но я могу предложить способ избежать хэширования и вместо ожидаемой сложности O(x*x*y) иметь сложность O(x*x*y) за счет стоимости из 10 ^ 6 дополнительной памяти. Рассматривая ограничения, которые вы предоставили, у вас будет не более 10 ^ 6 разных номеров. Итак, моя идея такова: сортируйте все числа, а затем их уникальные (удалите дубликаты). Назначьте уникальное число от 1 до 10 ^ 6 (или количество уникальных номеров) каждому из чисел (используя их порядок в отсортированном и уникальном массиве). После этого вместо hashmap on для каждой пары используйте бит-набор размером 10 ^ 6. Таким образом, у вас будет определенная сложность O(x*x*y) (так как предвычисление, которое я предлагаю, имеет сложность O(x * y *(log(x) + log (y))).