Prolog中列表的所有组合均不包含双打 [英] All combinations of a list without doubles in Prolog

问题描述

是否有一种简单的方法来获取列表的所有组合而没有双打.没有双打，我的意思是彼此也没有排列.因此，没有[a,b,c]和[c,a,b]或[c,b,a].

Is there a simple way of getting all the combinations of a list without doubles. Without doubles I mean also no permutations of each other. So no [a,b,c] and [c,a,b] or [c,b,a].

因此对于输入[a，b，c]，输出将为:

So for the input [a,b,c] the output would be:

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

我只能找到带有双打(排列)的解决方案

I can only find solutions WITH the doubles (permutations)

推荐答案

此问题的解决方案非常简单:空集中显然只有一个组合:空集:

The solution to this problem is rather simple: there is evidently only one combination out of the empty set: the empty set:

combs([],[]).

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

Furthermore for each element, you can decide whether you add it or not:

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

由于您按照列表的顺序进行选择(或放下)，因此可以保证您以后不会再次选择a.如果将其喂入[a,b,c]，它将永远不会生成[b,a,c]之类的东西，因为一旦决定拾取/放下a，它便无法添加b并重新确定a.

Since you pick (or drop) in the order of the list, this guarantees you that you later will not redecide to pick a. If you feed it [a,b,c], it will never generate something like [b,a,c], because once it has decided to pick/drop a, it cannot add b and re-decide on 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 = [].

如果您想以相反的方式生成它(对第一个放置元素进行更多的测试，而不是添加它们，您可以简单地交换递归语句):

In case you want to generate it the opposite way (have more of a test to first drop elements, instead of adding them, you can simply swap the recursive statements):

combs([],[]).

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

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

In that case the result will be:

?- 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].

编辑

鉴于您想排除空白列表，您可以简单地通过在通话中添加另一张支票来做到这一点:

EDIT

Given you want to exclude the empty list, either you can do it simply by adding another check in your call:

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

您可以在以下函数中定义它:

You can define this in a function like:

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

或通过重写comb/2函数.在这种情况下，最好使用 accumulator 来计算所选元素的当前数量:

Or by rewriting the comb/2 function. In that case you better use an accumulator that counts the current amount of selected elements:

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

combs_without_empty/3有点复杂.如果列表仅包含一个元素，则应检查N是否大于零.如果是这样，我们可以选择是否添加元素.如果N为零，我们必须将其包括在内.所以:

The combs_without_empty/3 is a bit more complicated. In case the list contains only one element, one should check if N is greater than zero. If that is the case, we can choose whether to add the element or not. If N is zero, we have to include it. So:

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

我们还必须实现一个递归部分，该部分将在给定元素的情况下递增N:

We also have to implement a recursive part that will increment N given we select an element:

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

将所有内容放在一起可以得到:

Putting it all together gives:

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.

这篇关于Prolog中列表的所有组合均不包含双打的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！