Prolog: how to get all the combinations

Question

I have the following for example:

bag(b1)
bag(b2)

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

Now i don't really understand how i can get all possibilities out of this? I must use all bags. Like i should get a list of lists like this:

[ [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 it must use all items. I know i can get the facts using findall, but then i'm 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'm clueless and i don't understand how to think to achieve such results.

Possible idea to get the 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 would need something like, get a combinations of the first bag and then, go to the next bag, take a combination, and if it's valid (all items used) append to the list, else go back to the first bag with another combination and so on... or are there better solutions ?

Thanks in advance!

Answer 1

You first define a predicate powset/3 that generates all powersets out of a given set and the not-selected elements as 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 a divide/3 command that given a list of items, divides it over 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 a ziptogether/3 utility, that zips two lists into a list of predicates:

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

You can do this 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 previous version using findall is active: it generates the entire list of configurations. In many cases lazy evaluation is better: it enables one to generate a limited number of instance. The lazy version is:

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 runs in O(b^n+b+n) with b the number of bins and n the number of bins and n the number of items.

Note: it is very likely some of the introduced predicates already exist in a lot of Prolog implementations, but since these predicates are not standardized, it is better to provide an implementation oneself.