Pertanyaan Prolog: bagaimana cara mendapatkan semua kombinasi


Saya memiliki yang berikut ini misalnya:

bag(b1)
bag(b2)

item(i1)
item(i2)
item(i3)
item(i4)

Sekarang saya tidak benar-benar mengerti bagaimana saya bisa mendapatkan semua kemungkinan dari ini? Saya harus menggunakan semua tas. Seperti saya harus mendapatkan daftar daftar seperti ini:

[ [together(b1, [i1,i2,i3,i4]), together(b2, [])] ,..., [together(b1, [i1]), together(b2, [i2,i3,i4])] [together(b1, [i1,i2]), together(b2, [i3,i4])] ] 

dll semua kemungkinan kombinasi tetapi harus menggunakan semua item. Saya tahu saya bisa menggunakan fakta findall, tapi kemudian saya terjebak

ini yang saya punya:

test(X) :-
findall(C, bag(C),Bags),
findall(K, item(K),Items),
something???

Setiap ide tentang di mana untuk memulai karena saya tidak mengerti dan saya tidak mengerti bagaimana cara berpikir untuk mencapai hasil seperti itu.

Ide yang memungkinkan untuk mendapatkan kombinasi:

item_combination(C) :-
    findall(I, item(I), Is),
    combination(Is, C).

combination(_, []).
combination(Set, [X|Xs]) :-
    select(X, Set, Set0),
    combination(Set0, Xs).

Saya akan membutuhkan sesuatu seperti, dapatkan kombinasi dari tas pertama dan kemudian, pergi ke tas berikutnya, ambil kombinasi, dan jika itu valid (semua item yang digunakan) tambahkan ke daftar, lain kembali ke tas pertama dengan kombinasi lain dan seterusnya ... atau apakah ada solusi yang lebih baik?

Terima kasih sebelumnya!


5
2017-12-12 09:17


asal


Jawaban:


Anda terlebih dahulu menentukan predikat powset/3 yang menghasilkan semua pembangkit listrik dari set yang diberikan dan elemen yang tidak dipilih sebagai daftar ketiga:

powset3([],[],[]).
powset3([H|T],T2,[H|T3]) :-
    powset3(T,T2,T3).
powset3([H|T],[H|T2],T3) :-
    powset3(T,T2,T3).

Selanjutnya, kita mendefinisikan a divide/3 perintah yang diberikan daftar item, membaginya N set:

divide(_,N,[]) :-
    N < 1.
divide(Items,1,[Items]).
divide(Items,N,[Selected|Other]) :-
    N > 1,
    powset3(Items,Selected,Rest),
    N1 is N-1,
    divide(Rest,N1,Other).

Dan akhirnya a ziptogether/3 utilitas, yang ritsleting dua daftar ke dalam daftar predikat:

ziptogether([],[],[]).
ziptogether([HA|TA],[HB|TB],[together(HA,HB)|TC]) :-
    ziptogether(TA,TB,TC).

Anda dapat melakukan ini dengan:

findall(I,item(I),Is),
findall(B,bag(B),Bs),
length(Bs,NB),
findall(Proposal,(divide(Is,NB,Ds),ziptogether(Bs,Ds,Proposal)),List).

Contoh:

?- findall(I,item(I),Is),
|        findall(B,bag(B),Bs),
|        length(Bs,NB),
|        findall(Proposal,(divide(Is,NB,Ds),ziptogether(Bs,Ds,Proposal)),List).
Is = [i1, i2, i3, i4],
Bs = [b1, b2],
NB = 2,
List = [[together(b1, []), together(b2, [i1, i2, i3, i4])], [together(b1, [i4]), together(b2, [i1, i2, i3])], [together(b1, [i3]), together(b2, [i1, i2, i4])], [together(b1, [i3, i4]), together(b2, [i1, i2])], [together(b1, [i2]), together(b2, [i1|...])], [together(b1, [i2|...]), together(b2, [...|...])], [together(b1, [...|...]), together(..., ...)], [together(..., ...)|...], [...|...]|...].

Versi malas:

Versi sebelumnya menggunakan findall aku s aktif: itu menghasilkan seluruh daftar konfigurasi. Dalam banyak kasus evaluasi malas lebih baik: memungkinkan seseorang menghasilkan jumlah instance yang terbatas. Versi malas adalah:

getBagConfig(Proposal) :-
    findall(I,item(I),Is),
    findall(B,bag(B),Bs),
    length(Bs,NB),
    divide(Is,NB,Ds),
    ziptogether(Bs,Ds,Proposal).

Kompleksitas waktu:  Algoritma berjalan dalam O (b ^ n + b + n) dengan b jumlah sampah dan n jumlah sampah dan jumlah item n.

catatan:  kemungkinan besar beberapa predikat yang diperkenalkan sudah ada dalam banyak implementasi Prolog, tetapi karena predikat ini tidak terstandardisasi, lebih baik menyediakan implementasi sendiri.


2
2017-12-12 13:51