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.

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

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屋！