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]

我只能找到包含双倍数（排列）的解决方案。

- Enforcerke

---

你能假设你不会输入一个列表 [a,b,a] 吗？ - Willem Van Onsem

如果我正确理解了这个问题，那么它是关于生成组合的。 - Willem Van Onsem

@GuyCoder：我认为他的意思是他想要在取值时不重复地获取所有组合，比如[a,a,a]不被枚举。 - Willem Van Onsem

除了接受投票外，您也可以给一个赞。 - Guy Coder

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.

- Willem Van Onsem

---

如果我直接阅读OP的问题，似乎他们不想将[]作为有效解决方案（？）。 - lurker

@Enforcerke: 在这种情况下，有两个选择，要么重写谓词; 要么在结尾处添加检查。我已经简要讨论了这两种情况。 - Willem Van Onsem

@WillemVanOnsem 谢谢，现在我明白了。所以基本上你知道对于递归的每个头，它要么被包含在内，要么被排除在外？ - Enforcerke

@Enforcerke：由于Prolog的自动分支，你可以选择是否包含它，但是后来你会返回并采取另一种选择。 - Willem Van Onsem

@Enforcerke：首先，您不能同时使用两个版本（除非将其中一个重命名）。我假设您的意思是使用一个版本。这是Prolog的基本特征之一：自动回溯：如果有多个头匹配，则所有头最终都将通过回溯枚举。 - Willem Van Onsem

Answer 2

在不使用额外的检查空列表的情况下，一个干净利落的解决方案就是从规则中排除空列表。基本情况应该是单个元素的组合：

comb_without_empty([H|_], [H]).   % Simple case of one element comb
comb_without_empty([_|T], C) :-   % Combinations of the tail w/o head
    comb_without_empty(T, C).
comb_without_empty([H|T], [H|C]) :-  % Combinations of the tail including head
    comb_without_empty(T, C).

| ?- comb_without_empty([a,b,c], L).

L = [a] ? a

L = [b]

L = [c]

L = [b,c]

L = [a,b]

L = [a,c]

L = [a,b,c]

(1 ms) no
| ?-

- lurker