11
$\begingroup$

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.)

$\endgroup$
1
  • 1
    $\begingroup$ Is the range/number of possible books finite? Can this "fingerprint" identification be done on the fly - as each book is added to some person's favorite list - or are you given the set of lists beforehand? $\endgroup$
    – Paresh
    Dec 7, 2012 at 11:23

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ +1 Of course you're right! :) It's not hard to construct examples where my greedy algorithm misses. Oops. $\endgroup$
    – Patrick87
    Dec 7, 2012 at 17:26
  • $\begingroup$ OP: 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. $\endgroup$
    – Merbs
    Dec 8, 2012 at 4:17
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ See Falk Huffner's answer, where he correctly identifies your problem as the NP-Hard Hitting Set problem. It appears my answer gives the usual greedy approximation for the problem, which isn't bad, but isn't optimal either. $\endgroup$
    – Patrick87
    Dec 7, 2012 at 17:27
0
$\begingroup$

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']}
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I placed your comment such that Falk would be notified. $\endgroup$
    – Merbs
    Dec 8, 2012 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.