Let's say we have 10 people, each with a list of favorite books. For a given person X, I would like to find a special subset of X's books liked only by X, i.e. there is no other person that likes all of the books in X's special subset. I think of this special subset as a unique "fingerprint" for X.
I would appreciate suggestions on an approach for finding such sets. (While this reads like a homework problem, it is related to a problem in my biology research that I am trying to solve.)
I assume you want the fingerprint to be as small as possible. Then this is the Hitting Set problem: For each person, make a list of all books liked by X but not by this person. Then, the goal is to select at least one book from each list. The problem is NP-hard, so you can't expect to find an algorithm that always solves it optimally in polynomial time. The greedy algorithm has a bad theoretical worst-case bound, but often works quite decent in practice. If you want to solve it optimally, an Integer Linear Programming solver should be able to solve instances of up to 1000 or maybe 10000 books. If you give more details on the size and structure of your instances, we could suggest other approaches.
This isn't a particularly clever algorithm, but it's polynomial, and I think it should work. Take any set. For each element in this set, count the number of remaining sets which do not contain it and remember which sets contain it. Pick the element with the highest count, and redo the counts for the remaining elements, ignoring the sets which lack the element you just chose. Continue until all remaining sets have been eliminated from consideration.
Example: let $A = \{1, 2, 3\}$, $B = \{2, 3, 4\}$, $C = \{2, 4, 6\}$, and $D = \{1, 3, 5\}$. Then we have counts $c_1 = 2$, $c_2 = 1$, and $c_3 = 1$. We choose 1, eliminating sets $B$ and $C$ which did not contain it; redoing the counts, we have $c_2 = 1$ and $c_3 = 0$. We choose 2 as the next element, and remove $D$ from consideration. We are now done, and our "fingerprint" set is $\{1, 2\}$. EDIT: to complete the example, you should get the other fingerprint sets to come out as $\{3, 4\}$, $\{6\}$, and $\{5\}$.
I haven't given this a lot of thought, but intuitively, it seems like it should work. The idea is to greedily take as the next element of the fingerprint set the item which covers the most uncovered sets.
Maybe I did not understand the question correcty (based on somewhat complicated answers), but here goes. You just go through all persons, and through all their books, that they like. You create a data structure (prefferably a Hash Map $M$), where key is the book and value is a list of persons who like this book. You fill this data structure in an intuitive way (for each person/book pair, you append person to list $M[book]$). Then you go through the map keys and where the length of the list is equal to one, then this book is one of the fingerprint books of this particular person.
Let me demonstrate on python code:
%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
The code prints:
{'Frank': ['X'], 'Matt': [], 'Andy': ['G'], 'Joe': ['B'], 'Anna': ['Y', 'Z']}
This is the OP (didn't register on initial submission, so now I can't comment properly). Thank you so much for the feedback -- the original greedy algorithm solution got me going in the right direction. The total space I'm working on concerns 100s of individuals and 1000s of "books" -- if this is feasible with the integer programming approach, I'd love to hear more about it.
