Нахождение подмножеств, которые могут быть завершены к кортежам без дубликатов
У нас есть набор наборов 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's, то это займет время. Вы знаете лучший алгоритм?
Править: вот пример. Взять
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 ответа
Думаю, здесь может помочь алгоритм присваивания. Основным шагом было бы зафиксировать число в одном из Ai, а затем посмотреть, можно ли использовать это число с другими, выбранными из Aj, чтобы выбрать число из каждого набора без повторения. Думайте о числах как о людях, а о числах в наборе Aj как о людях, которых можно использовать для выполнения задачи j. Тогда проблема поиска разных представителей от каждого Aj - это проблема назначения разных людей для каждой задачи.
Википедия рассматривает проблему назначения как имеющую все возможные назначения и стоимость каждого http://en.wikipedia.org/wiki/Assignment_problem . В нашем случае мы можем использовать 0 и 1 в качестве затрат, чтобы означать, что можно делать и чего нельзя делать, и посмотреть, есть ли ответ с нулевой стоимостью.
Я все еще думаю, как решить эту проблему, но я решил попробовать переписать вопрос, чтобы посмотреть, даст ли он мне какое-нибудь вдохновение.
Дано множество из 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