Как найти неидентичные элементы из нескольких векторов?

Question

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

Например, если заданы наборы a, b, c, d как:

a <- (1,3,5); 
b <- (3,6,8); 
c <- (2,3,4); 
d <- (2,4,6)

Я могу найти такие наборы, как (1, 8, 4, 6) или (3, 6, 2, 4) ..... на самом деле, мне нужно только найти один такой набор, чтобы доказать существование.

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

Есть ли более умные способы?Спасибо!

Answer 1

Вы можете переформулировать свою проблему как соответствие в двудольном графе:

• узел левой стороны - ваши множества,
• узлом с правой стороны являются целые числа, появляющиеся в наборах.

Существует грань между узлом "set" и узлом "integer", если набор содержит данное целое число. Затем вы пытаетесь найти соответствие в этом двудольном графе: каждый набор будет связан с одним целым числом, и никакое целое число не будет использоваться дважды. Время выполнения простого алгоритма для нахождения такого соответствия составляет O (| V || E |), здесь | V | меньше (m + 1) k и | E | равно мк. Таким образом, у вас есть решение в O (m ^ 2 k ^ 2). См .: Соответствие в двудольных графах .

Алгоритм двустороннего сопоставления:

Алгоритм работает на ориентированных графах. В начале все ребра ориентированы слева направо. Два узла будут сопоставлены, если ребро между ними будет ориентировано справа налево, поэтому в начале совпадение будет пустым. Цель алгоритма состоит в том, чтобы найти «дополнительные пути» (или альтернативные пути), то есть пути, которые увеличивают размер сопоставления.

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

Вот как вы найдете путь расширения:

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

Если вы не можете найти расширяющий путь, то сопоставление является оптимальным.

Поиск пути расширения имеет сложность O (| E |), и вы делаете это самое большее мин (k, m) раз, поскольку размер наилучшего совпадения ограничен k и m. Поэтому для вашей задачи сложность будет O (mk min (m, k)).

Вы также можете увидеть эту ссылку , раздел 1., для более полного объяснения с доказательствами.