Prologue: how to get all combinations

Question

I have the following:

bag(b1) bag(b2) item(i1) item(i2) item(i3) item(i4) 

Now I really don’t understand how I can take all the opportunities from this? I have to use all the bags. For example, I should get a list of such lists:

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

etc. all possible combinations , but he must use all the elements . I know I can get facts with findall , but then I got stuck

this is what i have:

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

Any ideas on where to start because I don’t know and I don’t understand how to think in order to achieve such results.

Possible idea to get a combination:

 item_combination(C) :- findall(I, item(I), Is), combination(Is, C). combination(_, []). combination(Set, [X|Xs]) :- select(X, Set, Set0), combination(Set0, Xs). 

I need something like: get a combination of the first bag, and then go to the next bag, take the combination, and if it is valid (all used items) is added to the list, return to the first bag with a different combination, etc ... or are there any better solutions?

Thanks in advance!

Answer 1

First, you define the predicate powset/3 , which generates all the power elements from the given set and elements not selected as the third list:

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

Next, we define the divide/3 command, which sets the list of elements, divides it into N sets:

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

And finally, the ziptogether/3 utility, which fastens two lists into a predicate list:

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

You can do it with

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

Example:

 ?- 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(..., ...)|...], [...|...]|...]. 

lazy version :

The latest version using findall is active: it generates an entire list of configurations. In many cases, a lazy score is better: it allows you to generate a limited number of instances. Lazy version:

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

---

Time complexity: the algorithm works in O (b ^ n + b + n), b is the number of boxes and n is the number of boxes and n is the number of elements.

Note. . Most likely, some of the introduced predicates already exist in many implementations of Prolog, but since these predicates are not standardized, it is better to provide an implementation.