Prolog中的子集

Question

我正在寻找一个像这样工作的谓词:

?- subset([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [2, 3] ;
...

我已经看到了一些subset实现,但是当你想检查一个列表是否是另一个列表的子集时,它们都可以工作,而不是在你想要生成子集时.有任何想法吗？

Answer 1

这是一个实现:

subset([], []).
subset([E|Tail], [E|NTail]):-
  subset(Tail, NTail).
subset([_|Tail], NTail):-
  subset(Tail, NTail).

它将生成所有子集,但不是按照示例中显示的顺序生成.

根据评论者的要求,这里有一个解释:

第一个条款是基本情况.它声明空列表是空列表的子集.

第二和第三个条款涉及递归.第二个子句指出,如果两个列表具有相同的头部且右侧列表的尾部是左侧列表尾部的子集,则右侧列表是左侧列表的子集.

第三个子句指出,如果我们跳过左侧列表的头部,右侧列表是左侧列表尾部的子集,则右侧列表是左侧列表的子集.

上面显示的过程生成有序集.对于无序集,您可以使用permutation/3:

unordered_subset(Set, SubSet):-
  length(Set, LSet),
  between(0,LSet, LSubSet),
  length(NSubSet, LSubSet),
  permutation(SubSet, NSubSet),
  subset(Set, NSubSet).

Answer 2

在http://www.probp.com/publib/listut.html上,您将找到一个谓词的实现,该谓词subseq0可以执行您想要的操作:

subseq0(List, List).
subseq0(List, Rest) :-
   subseq1(List, Rest).

subseq1([_|Tail], Rest) :-
   subseq0(Tail, Rest).
subseq1([Head|Tail], [Head|Rest]) :-
   subseq1(Tail, Rest).

一个简短的解释:subseq0(X, Y)检查Y是否是X 的子集子序列,同时subseq1(X, Y)检查Y是否是X 的正确 子集子序列.

由于集合的默认表示是具有唯一元素的列表,因此您可以使用它来获取所有子集,如以下示例所示:

?- subseq0([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 3] ;
X = [3] ;
X = [] ;
X = [2] ;
X = [1, 3] ;
X = [1] ;
X = [1, 2] ;
false.