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

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

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

第一个子句是基本情况。它指出空列表是空列表的子集。

第二个和第三个子句涉及递归。第二个子句指出，如果两个列表具有相同的 Head，并且右列表的尾部是左列表尾部的子集，则右列表是左列表的子集。

第三个子句指出，如果我们跳过左列表的头部，并且右列表是左列表尾部的子集，则右列表是左列表的子集。

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

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