Prolog中没有双打的列表的所有组合

Question

有没有一种简单的方法可以在没有双打的情况下获取列表的所有组合。没有双打，我的意思是也没有彼此的排列。所以没有[a,b,c]和[c,a,b]或[c,b,a]。

所以对于输入 [a,b,c] 输出将是：

[a]
[b]
[c]
[a,b]
[a,c]
[b,c]
[a,b,c]

我只能找到双打（排列）的解决方案

Answer 1

这个问题的解决方案相当简单：显然空集中只有一个组合：空集：

combs([],[]).

此外，对于每个元素，您可以决定是否添加它：

combs([H|T],[H|T2]) :-
    combs(T,T2).
combs([_|T],T2) :-
    combs(T,T2).

由于您按列表的顺序选择（或删除），这可以保证您以后不会重新决定选择a。如果你喂它[a,b,c]，它永远不会产生类似的东西[b,a,c]，因为一旦它决定选择/删除a，它就不能添加b和重新决定a。

运行这个给出：

?- combs([a,b,c],L).
L = [a, b, c] ;
L = [a, b] ;
L = [a, c] ;
L = [a] ;
L = [b, c] ;
L = [b] ;
L = [c] ;
L = [].

如果你想以相反的方式生成它（有更多的测试来首先删除元素，而不是添加它们，你可以简单地交换递归语句）：

combs([],[]).

combs([_|T],T2) :-
    combs(T,T2).
combs([H|T],[H|T2]) :-
    combs(T,T2).

在这种情况下，结果将是：

?- combs([a,b,c],L).
L = [] ;
L = [c] ;
L = [b] ;
L = [b, c] ;
L = [a] ;
L = [a, c] ;
L = [a, b] ;
L = [a, b, c].

编辑

鉴于您想排除空列表，您可以简单地通过在调用中添加另一个检查来完成：

?- combs([a,b,c],L),L \= [].

您可以在如下函数中定义它：

combs_without_empty1(LA,LB) :-
    combs_without_empty1(LA,LB),
    LB \= [].

或者通过重写comb/2函数。在这种情况下，您最好使用一个累加器来计算当前所选元素的数量：

combs_without_empty(L,C) :-
    combs_without_empty(L,0,C).

该combs_without_empty/3是一个比较复杂。如果列表仅包含一个元素，则应检查是否N大于零。如果是这种情况，我们可以选择是否添加元素。如果N为零，我们必须包括它。所以：

combs_without_empty([A],_,[A]).
combs_without_empty([_],N,[]) :-
    N > 0.

我们还必须实现一个递归部分，该部分将N在我们选择一个元素时递增：

combs_without_empty([_|T],N,T2) :-
    combs_without_empty(T,N,T2).
combs_without_empty([H|T],N,[H|T2]) :-
    N1 is N+1,
    combs_without_empty(T,N1,T2).

把它们放在一起给出：

combs_without_empty(L,C) :-
    combs_without_empty(L,0,C).

combs_without_empty([A],_,[A]).
combs_without_empty([_],N,[]) :-
    N > 0.

combs_without_empty([_|T],N,T2) :-
    combs_without_empty(T,N,T2).
combs_without_empty([H|T],N,[H|T2]) :-
    N1 is N+1,
    combs_without_empty(T,N1,T2).

其中产生：

?- combs_without_empty([a,b,c],L).
L = [c] ;
L = [b, c] ;
L = [b] ;
L = [a, c] ;
L = [a] ;
L = [a, b, c] ;
L = [a, b] ;
false.