Prolog:如何获得所有组合

Question

例如，我有以下内容:

bag(b1)
bag(b2)

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

现在我真的不明白如何从中获得所有可能性？我必须使用所有袋子。
就像我应该得到这样的列表:
[
[together(b1, [i1,i2,i3,i4]), together(b2, [])]
,...,
[together(b1, [i1]), together(b2, [i2,i3,i4])]
[together(b1, [i1,i2]), together(b2, [i3,i4])]
]
等所有可能的组合 但它必须使用所有项目 .我知道我可以使用 findall 了解事实，但后来我被卡住了

这就是我所拥有的:

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

关于从哪里开始的任何想法，因为我一无所知，我不明白如何思考才能实现这样的结果。

获得组合的可能想法:

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

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

我需要类似的东西，获得第一个袋子的组合，然后转到下一个袋子，进行组合，如果有效(使用的所有项目)附加到列表中，否则返回到第一个袋子与另一个组合等等......或者有更好的解决方案吗？

提前致谢!

Answer 1

您首先定义一个谓词 powset/3从给定集合中生成所有幂集，并将未选择的元素作为第三个列表:

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

接下来，我们定义一个 divide/3给出项目列表的命令，将其划分为 N套:

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

最后是 ziptogether/3实用程序，将两个列表压缩为谓词列表:

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

你可以这样做:

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

示例:

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

懒人版 :

以前的版本使用 findall处于事件状态:它生成整个配置列表。在许多情况下，惰性求值更好:它可以生成有限数量的实例。懒人版是:

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

时间复杂度:该算法在 O(b^n+b+n) 中运行，其中 b 为 bin 数量，n 为 bin 数量，n 为项目数。

注:很多Prolog实现中很可能已经存在一些引入的谓词，但是由于这些谓词没有标准化，因此最好自己提供一个实现。