Prolog - 子集

Question

我对 Prolog 有点陌生。我正在尝试编写一个函数subset(Set, Subset) 来确定Subset 是否是Set 的子集(duh)。另外，如果第二个参数没有实例化，它应该输出每个可能的子集。现在，当两个参数都被实例化时它就可以工作，但是当我尝试输出所有子集时，它遇到了 member/2 的问题。例如:

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

这是我的代码:

% subset/2
% subset(Set, Subset) iff Subset is a subset of Set
subset(_, []).
subset(Set, [H|T]) :-
  member(H, Set),
  subset(Set, T).

如何让成员不会一直选择 Set 中的第一个选项？

Answer 1

(包括 SICStus 和 SWI 在内的许多 Prolog 系统在其库中都有一个 subset/2 ，而是 subset(Subset, Set) ；而且它也不是一个干净的关系...)

这完全取决于你所说的集合的含义。 [1, 1] 是一个有效的集合吗？它们必须以一种顺序发生吗？如果您允许重复，您的定义就很好。毕竟你的定义如下:

set_subset(Set, Subset): All elements of Subset are elements of Set

令您感到相当惊讶的是，您现在拥有无限的解决方案。更糟糕的是，该集合的枚举方式非常不公平。如果您只担心所列举的精确顺序解决方案，请考虑:

?- length(Subset,N), set_subset([1,2,3], Subset).
   Subset = [], N = 0
;  Subset = [1], N = 1
;  Subset = [2], N = 1
;  Subset = [3], N = 1
;  Subset = [1, 1], N = 2
;  Subset = [1, 2], N = 2
;  Subset = [1, 3], N = 2
;  Subset = [2, 1], N = 2
;  Subset = [2, 2], N = 2
;  Subset = [2, 3], N = 2
;  false.

如果您希望该子集具有有限多个解决方案，您可能需要一个子序列。请参阅this answer .