Menemukan set "sidik jari"

Katakanlah kita memiliki 10 orang, masing-masing dengan daftar buku favorit. Untuk orang tertentu X, saya ingin menemukan subset khusus dari buku X yang hanya disukai oleh X, yaitu tidak ada orang lain yang menyukai semua buku dalam subset khusus X. Saya menganggap subset khusus ini sebagai "sidik jari" unik untuk X.

Saya akan menghargai saran tentang pendekatan untuk menemukan set tersebut. (Walaupun ini terbaca seperti masalah pekerjaan rumah, ini terkait dengan masalah dalam penelitian biologi yang saya coba selesaikan.)

Saya berasumsi Anda ingin sidik jari menjadi sekecil mungkin. Maka ini adalah masalah Hitting Set : Untuk setiap orang, buat daftar semua buku yang disukai oleh X tetapi tidak oleh orang ini. Kemudian, tujuannya adalah untuk memilih setidaknya satu buku dari setiap daftar. Masalahnya adalah NP-hard, jadi Anda tidak bisa berharap untuk menemukan algoritma yang selalu menyelesaikannya secara optimal dalam waktu polinomial. Algoritma serakah memiliki teori buruk terburuk terikat, tetapi sering bekerja cukup baik dalam praktiknya. Jika Anda ingin menyelesaikannya secara optimal, pemecah Integer Linear Programming harus dapat memecahkan contoh hingga 1000 atau mungkin 10.000 buku. Jika Anda memberikan detail lebih lanjut tentang ukuran dan struktur instans Anda, kami dapat menyarankan pendekatan lain.

Ini bukan algoritma yang sangat pintar, tetapi jumlahnya banyak, dan saya pikir itu harus bekerja. Ambil satu set. Untuk setiap elemen dalam set ini, hitung jumlah set yang tersisa yang tidak mengandungnya dan ingat set mana yang berisi itu. Pilih elemen dengan jumlah tertinggi, dan ulangi jumlah untuk elemen yang tersisa, abaikan set yang tidak memiliki elemen yang baru saja Anda pilih. Lanjutkan sampai semua set yang tersisa dihilangkan dari pertimbangan.

Contoh: misalkan , , , dan . Kemudian kita memiliki jumlah , , dan . Kami memilih 1, menghilangkan set dan yang tidak mengandungnya; mengulangi penghitungan, kita memiliki dan . Kami memilih 2 sebagai elemen berikutnya, dan menghapus dari pertimbangan. Kita sekarang selesai, dan set "sidik jari" kami adalah . Sunting: untuk melengkapi contoh, Anda harus mendapatkan set sidik jari lainnya untuk keluar sebagai ,$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${ 3 , 4 } { 6 } { 5 $\{1, 2\}$$\{3, 4\}$$\{6\}$ , dan .$\{5\}$

Saya belum banyak memikirkan hal ini, tetapi secara intuitif, sepertinya ini seharusnya berhasil. Idenya adalah dengan rakus mengambil sebagai elemen berikutnya dari sidik jari mengatur item yang mencakup set yang paling terbuka.

Mungkin saya tidak mengerti pertanyaan dengan benar (berdasarkan jawaban yang agak rumit), tetapi begini. Anda cukup membaca semua orang, dan membaca semua buku mereka, yang mereka sukai. Anda membuat struktur data (lebih disukai Hash Map ), di mana kuncinya adalah buku dan nilainya adalah daftar orang-orang yang menyukai buku ini. Anda mengisi struktur data ini dengan cara yang intuitif (untuk setiap pasangan orang / buku, Anda menambahkan orang ke daftar ). Kemudian Anda pergi melalui tombol peta dan di mana panjang daftar sama dengan satu, maka buku ini adalah salah satu dari orang tertentu ini.M [ b o o k $M$$M[book]$fingerprint books

Biarkan saya menunjukkan pada kode python:

%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

Kode dicetak:

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

Ini adalah OP (tidak mendaftar pada pengiriman awal, jadi sekarang saya tidak bisa berkomentar dengan benar). Terima kasih banyak atas umpan baliknya - solusi algoritma serakah yang asli membuat saya bergerak ke arah yang benar. Total ruang yang saya kerjakan menyangkut 100-an individu dan 1000-an "buku" - jika ini layak dengan pendekatan pemrograman bilangan bulat, saya ingin mendengar lebih banyak tentang hal itu.