Поиск подмножеств, которые можно дополнить кортежами без дубликатов - PullRequest
Новая
       27

Поиск подмножеств, которые можно дополнить кортежами без дубликатов

5 голосов
/ 06 мая 2010

У нас есть набор множеств A_1, .., A_n. Цель состоит в том, чтобы найти новые наборы для каждого из старых наборов. 

newA_i = {a_i in A_i such that there exist (a_1,..,a_n) in (A1,..,An) with no a_k = a_j for all k and j}

Итак, это говорит о том, что мы удаляем из A_i все элементы, которые нельзя использовать для формирования кортежа (a_1, .. a_n) из наборов (A_1, .., A_n), так что кортеж не ' не содержит дубликатов.

Мой вопрос заключается в том, как быстро вычислить эти новые наборы. Если вы просто реализуете это определение, генерируя все возможные v, это займет экспоненциальное время. Знаете ли вы лучший алгоритм?

Редактировать: вот пример. Возьми 

A_1 = {1,2,3,4}
A_2 = {2}.

Теперь новые наборы выглядят так: 

newA_1 = {1,3,4}
newA_2 = {2}

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

Другой пример: 

A_1 = {1,2,3}
A_2 = {1,4,5}
A_3 = {2,4,5}
A_4 = {1,2,3}
A_5 = {1,2,3}

Теперь новые наборы: 

newA_1 = {1,2,3}
newA_2 = {4,5}
newA_3 = {4,5}
newA_4 = {1,2,3}
newA_5 = {1,2,3}

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

Эта проблема кажется сложной, но было бы здорово, если бы существовал алгоритм с полиномиальным временем.

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

Ответы [ 2 ]

2 голосов
/ 07 мая 2010

Я все еще думаю о том, как решить эту проблему, но я решил попробовать переписать вопрос, чтобы посмотреть, не вдохновил ли он меня.

Данный набор из N наборов: 

A_i = {a_i0, a_i1, ..., a_ij, ...}

найти 

B_i such that x is in B_i if and only if:
   x is in A_i and
   there exists {c_0, c_1, c_2, c_3, ..., c_N} such that
      c_i = x and
      c_k is in A_k for all k and
      c_k != c_l for all k != l
2 голосов
/ 06 мая 2010

Я думаю, что алгоритм назначения может помочь здесь. Основным шагом было бы зафиксировать номер в одном из Ai, а затем посмотреть, можно ли использовать этот номер с другими, выбранными из Aj, чтобы выбрать номер из каждого набора без повторения. Думайте о числах как о людях, а числа в наборе Aj как о людях, которых можно использовать для выполнения задачи j. Тогда проблема нахождения разных представителей от каждого Aj - это проблема назначения разных людей для каждой задачи.

Википедия рассматривает проблему назначения как наличие всех возможных назначений и стоимости для каждого http://en.wikipedia.org/wiki/Assignment_problem. В нашем случае мы можем использовать 0 и 1, поскольку значения означают, что можно, а что нельзя, и посмотрим, есть ли ответ с нулевой стоимостью.

...