Znajdowanie zestawów „odcisków palców”

Załóżmy, że mamy 10 osób, każda z listą ulubionych książek. Dla danej osoby X chciałbym znaleźć specjalny podzbiór książek X, lubiany tylko przez X, tzn. Nie ma innej osoby, która polubiłaby wszystkie książki w specjalnym podzbiorze X. Uważam ten specjalny podzbiór za unikalny „odcisk palca” dla X.

Byłbym wdzięczny za sugestie dotyczące znalezienia takich zestawów. (Chociaż brzmi to jak zadanie domowe, jest ono związane z problemem w moich badaniach biologicznych, który próbuję rozwiązać.)

Zakładam, że chcesz, aby odcisk palca był jak najmniejszy. To jest to Uderzanie Set Problem: Dla każdej osoby, zrobić listę wszystkich książek lubianych przez X, ale nie przez tę osobę. Następnie celem jest wybranie co najmniej jednej książki z każdej listy. Problem jest trudny dla NP, więc nie można oczekiwać algorytmu, który zawsze rozwiąże go optymalnie w czasie wielomianowym. Chciwy algorytm ma słabą teoretyczną granicę najgorszego przypadku, ale często działa całkiem przyzwoicie w praktyce. Jeśli chcesz rozwiązać go optymalnie, solver do programowania liniowego w liczbach całkowitych powinien być w stanie rozwiązać instancje do 1000, a może 10000 książek. Jeśli podasz więcej szczegółów na temat wielkości i struktury swoich instancji, możemy zasugerować inne podejścia.

To nie jest szczególnie sprytny algorytm, ale jest wielomianowy i myślę, że powinien działać. Weź dowolny zestaw. Dla każdego elementu w tym zestawie policz liczbę pozostałych zestawów, które go nie zawierają i pamiętaj, które zestawy je zawierają. Wybierz element o największej liczbie i powtórz liczbę pozostałych elementów, ignorując zestawy, w których brakuje elementu, który właśnie wybrałeś. Kontynuuj, dopóki wszystkie pozostałe zestawy nie zostaną uwzględnione.

$A = \{1, 2, 3\}$$B = \{2, 3, 4\}$$C = \{2, 4, 6\}$$D = \{1, 3, 5\}$$c_1 = 2$$c_2 = 1$$c_3 = 1$$B$$C$$c_2 = 1$$c_3 = 0$$D$$\{1, 2\}$$\{3, 4\}$$\{6\}$$\{5\}$

Nie zastanawiałem się nad tym, ale intuicyjnie wydaje się, że powinno to działać. Chodzi o to, aby łapczywie przyjąć jako następny element zestawu odcisków palców element, który obejmuje najbardziej odkryte zestawy.

$M$$M[book]$fingerprint books

Pokażę kod Pythona:

%persons with books they like (it could also be a list or a set)
joe='ABCD'
andy='CDG'
frank='AHX'
anna='HAYZ'
matt='ACH'
%just transformation form variables, to names
names={joe:"Joe",andy:"Andy",frank:"Frank",anna:"Anna", matt:"Matt"}
%the map, from books to persons who like this book
books={}

%for each person
for p in names:
    %go through his liked books
    for book in p:
        %if book is already in the map, then append the person
        if book in books:
            books[book].append(names[p])
        else:
            %if not, then create a new book, and append the current person
            books[book]=[names[p]]

%create the fingerprint map (from person to books he likes)
fingerprint={}

%for each person create an empty list
for p in names:
    fingerprint[names[p]]=[]

%for each book in the map
for book in books:
    %if only one person likes this book, then it must be a part of his fingerprint
    if len(books[book])==1:
        fingerprint[books[book][0]].append(book)

print fingerprint

Kod drukuje:

{'Frank': ['X'], 'Matt': [], 'Andy': ['G'], 'Joe': ['B'], 'Anna': ['Y', 'Z']}

To jest OP (nie zarejestrował się przy pierwszym przesłaniu, więc teraz nie mogę poprawnie skomentować). Dziękuję bardzo za opinie - oryginalne rozwiązanie chciwego algorytmu poprowadziło mnie we właściwym kierunku. Całkowita przestrzeń, nad którą pracuję, dotyczy setek osób i tysiąca „książek” - jeśli jest to wykonalne przy podejściu do programowania liczb całkowitych, chciałbym usłyszeć o tym więcej.