Prolog中的子集 [英] Subsets in Prolog

问题描述

我正在寻找这样的谓词:

I'm looking for a predicate that works as this:

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

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

I've seen some subset implementations, but they all work when you want to check if one list is a subset of the another, not when you want to generate the subsets. Any ideas?

推荐答案

以下是实现:

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

它会生成所有子集，尽管不会按照示例中显示的顺序生成.

It will generate all the subsets, though not in the order shown on your example.

根据评论者的请求在此处进行说明:

As per commenter request here goes an explanation:

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

The first clause is the base case. It states that the empty list is a subset of the empty list.

第二和第三子句处理递归.第二个子句指出，如果两个列表具有相同的标题，并且右列表的尾部是左列表的尾部的子集，那么右列表是左列表的子集.

The second and third clauses deal with recursion. The second clause states that if two lists have the same Head and the tail of the right list is a subset of the tail of the left list, then the right list is a subset of the left list.

第三个子句指出，如果我们跳过左侧列表的开头，而右侧列表是左侧列表尾部的子集，那么右侧列表就是左侧列表的子集.

The third clause states that if we skip the head of the left list, and the right list is a subset of the tail of the left list, then the right list is a subset of the left list.

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

The procedure shown above generates ordered sets. For unordered sets you might use permutation/3:

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

这篇关于Prolog中的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！