Prolog - 子集

Question

Prolog - 子集

4

我对Prolog不太熟悉。我正在尝试编写一个函数subset(Set, Subset)，以确定Subset是否是Set的子集（显然）。此外，如果第二个参数未实例化，则应输出所有可能的子集。目前，当两个参数都实例化时，它可以正常工作，但是当我尝试输出所有子集时，它会遇到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中的第一个选项？

- Chris Phillips

3

（"duh"）这个名称相当令人困惑：考虑改用set_subset(Set, Subset)。 - false

3

请注意，你评论中的 iff 并不准确，因为 Set = any, Subset = [] 等情况下也成立。因此，请简单使用 if 代替。 - false

可能是Prolog中的子集的重复问题。 - user502187

2个回答

2

为了枚举子集，我认为不必生成排列，毕竟一个集合不应该关心顺序。因此，典型的教科书解决方案是：文本书。

% subset(-Set, +Set)
subset([X|L], [X|R]) :-
   subset(L, R).
subset(L, [_|R]) :-
   subset(L, R).
subset([], []).

与其他解决方案相比，这个解决方案：

这个解决方案：

?- subset(X, [1,2,3]), write(X), nl, fail; true.
[1,2,3]
[1,2]
[1,3]
[1]
[2,3]
[2]
[3]
[]

其他人的解决方案如下：

capellis

?- subset([1,2,3], X), write(X), nl, fail; true.
[]
[1]
[1,2]
[1,2,3]
[1,3]
[1,3,2]
[2]
[2,1]
[2,1,3]
[2,3]
[2,3,1]
[3]
[3,1]
[3,1,2]
[3,2]
[3,2,1]

从集合论中，我们知道| P（A）| = 2 ^ | A |，因此对于3元素长的输入子集应该生成8个子集。这就是此解决方案所做的，但其他解决方案枚举了太多冗余子集。

- user502187

2

你正在使用反转的参数来定义子序列。这将包括许多冗余的解决方案，例如 subset(X, [a,a,a])。 - false

Prolog 中也没有多重集合，例如 [1,2] 和 [2,1]。 - false

如果你想要非冗余的解决方案，你需要调用 sort([a,a,a], Y), subset(X, Y)，subset/2 谓词不会有任何改变。sort/2 是 ISO 核心标准的一部分。 - user502187

在Jekejeke Prolog中，您可以使用sys_distinct/2代替sort/2。该谓词尝试保留输入顺序并删除重复项。另请参阅：https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/frequent/standard/sort.p#L77 - user502187

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- false · Accepted Answer

许多Prolog系统包括SICStus和SWI在其库中都有一个subset/2，但更好的方法是使用subset(Subset, Set)；并且这也不是一个干净的关系......这完全取决于您对集合的定义。 [1, 1]是一个有效的集合吗？它们必须以一种顺序或另一种顺序出现吗？如果允许重复，则您的定义是正确的。毕竟，您的定义如下： set_subset(Set, Subset)：所有Subset的元素都是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.

如果你希望Subset有有限多个解，那么你可能更想要一个子序列。请参见这个答案。