Znajdowanie podzbiorów, które można uzupełnić do krotek bez duplikatów

Question

Posiadamy kolekcję zestawów A_1, .., A_n. Celem jest znalezienie nowych zestawów dla każdego ze starych zestawów.

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} 

Więc słownie ten mówi, że możemy usunąć wszystkie elementy z A_i, które nie mogą być wykorzystane do utworzenia krotki (a_1 .. a_n) z zestawów (a_1, .., a_n) taki, że krotka nie zawiera duplikatów.

Moje pytanie brzmi: jak szybko obliczyć te nowe zestawy. Jeśli zaimplementujesz tę definicję, generując wszystkie możliwe v, zajmie to czas wykładniczy. Czy znasz lepszy algorytm?

Edytuj: oto przykład. Weź

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

Teraz nowe zestawy wyglądać następująco:

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

2 został usunięty z a_1 bo jeśli go wybrać krotka zawsze będzie (2,2), które jest nieważne, ponieważ zawiera duplikaty. Z drugiej strony 1,3,4 są ważne, ponieważ (1,2), (3,2) i (4,2) są ważnymi krotkami.

Inny przykład:

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} 

Teraz nowe zestawy są:

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

W 1 i 2 są usuwane z zestawów 2 i 3, ponieważ jeśli wybierzesz 1 lub 2 z tych zestawów ty Zostaną tylko 2 wartości dla zestawów 1, 4 i 5, więc zawsze będziesz mieć duplikaty w krotkach, które wyglądają jak (_,1,_,_,_) lub jak (_,_,2,_,_).

Ten problem wydaje się trudny, ale byłoby wspaniale, gdyby istniał algorytm wielomianowy.

Innym sposobem, aby to spojrzeć, jest zobrazowanie zbiorów A_i po lewej stronie i wartości po prawej stronie, z linią łączącą zestaw z wartością, jeśli wartość jest w zbiorze.

Answer 1

Myślę, że algorytm przydziału może pomóc tutaj. Podstawowym krokiem byłoby ustalenie liczby w jednej z Ai, a następnie sprawdzenie, czy ta liczba może być używana z innymi wybranymi z Aj, aby wybrać liczbę z każdego zestawu bez powtórzenia. Pomyśl o liczbach jako o osobach, a liczbach z zestawu Aj jako o osobach, które mogą być użyte do wykonania zadania. Wtedy problem ze znalezieniem innego przedstawiciela z każdego Aj jest problemem przypisania innej osoby do każdego zadania.

Wikipedia traktuje zadanie przypisania jako mające wszystkie zadania możliwe i koszt dla każdego http://en.wikipedia.org/wiki/Assignment_problem. W naszym przypadku możemy użyć wartości 0 i 1, ponieważ koszty mogą być średnie i nie można tego zrobić i sprawdzić, czy odpowiedź jest zerowa.

Answer 2

Nadal zastanawiam się, jak rozwiązać ten problem, ale postanowiłem spróbować napisać to pytanie, aby sprawdzić, czy dało mi to jakąś inspirację.

otrzymuje zbiór N ustawia:

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

znaleźć

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