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 实现中，但是由于这些谓词没有标准化，所以最好自己提供一个实现。