适当子集 - Prolog

Question

适当子集 - Prolog

6

我正在尝试编写一个程序，该程序接受两个列表作为输入并检查是否为正确的子集。我开始使用以下代码：

proper([A],[]).
proper([],[A]).
proper([A|T1],[A|T2]) :- proper(T1,T2).

这对于顺序完全相同的输入非常有效。例如：

?- proper([a,b,c],[a,b,c,d]).
Yes

但是对于如下输入：

?- proper([a,b,c],[b,d,a,c]).
No

在查看了该网站后，我找到了一个之前提出的问题：

Prolog中的子集函数

这让我修改了我的代码，如下所示：

proper([A],[]).
proper([],[A]).
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2).
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2).

这对于子集是有效的，但对于真子集却不行。我认为我的问题出在我对proper/4的第二个子句工作原理的理解上。感谢任何帮助。

编辑:

我意识到我试图确定第一个列表是否是第二个列表的真子集并且第二个列表是第一个列表的真子集。清理了代码以更加准确。

proper([],_).
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2).
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2).

- Shrp91

2

只需对列表进行排序。这是最明智的做法，也是标准库处理它的方式。 - user1812457

@Boris，你能告诉我标准库中用于判断真子集的谓词吗？ - Shon

@aBathologist 请查看库(ordsets)（例如，在SWI-Prolog实现中）及其源代码。没有“proper”子集的谓词，但仅查看长度应该足够好，正如您在答案中已经指出的那样。 - user1812457

1

@aBathologist 我的意思主要是，当“集合”被表示为Prolog列表时，唯一明智的处理方式是保持列表排序。列表是嵌套术语，只能按一定方向遍历。 - user1812457

@Boris 我明白了！这是一个重要的观点。我只是认为我可能一直在忽略一个库或者有一种特殊的使用sort来完成正确子集检查的方法，但我无法完全理解。感谢您的详细说明。 - Shon

1个回答

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

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

- Shon · Accepted Answer

如果我理解正确，您在最后一次尝试中的前两个声明意味着，一个只有1个元素的列表是空列表的真子集（false），空列表是具有一个元素的列表的真子集（true）；第一个声明应该有问题，因为proper([1], [])和proper([], [1])都将成功，但真子集关系是不对称的。

我认为您的第二次尝试之所以无法过滤掉相同的子集，是因为没有声明要求A比B小。

以下是我想出的一些可能的解决方案。我使用smaller_set/2几次来增加清晰度和简洁性。

smaller_set(A, B) :-
    length(A, LA),
    length(B, LB),
    LA < LB.

def_proper_subset/2试图捕捉子集的标准定义。

def_proper_subset(A, B) :-
    smaller_set(A, B),                    % if A < B then there's some _e in B that isn't in A.
    forall(member(_e, A), member(_e, B)).

一个基于从A和B中删除每个匹配元素的递归定义的示例。它通过只在A在B之前耗尽元素时才成功来确保A < B。

rec_proper_subset1([], [_|_]).
rec_proper_subset1([_e|A], B) :-
    select(_e, B, C),            % C is B with _e removed. Only true if _e is in B.
    rec_proper_subset1(A, C).

在主谓语已经确认 A < B 后，这个使用辅助谓语来检查成员资格的函数。

rec_proper_subset2(A, B) :-
    smaller_set(A, B),
    rec_proper_subset2_(A, B).

rec_proper_subset2_([], _).
rec_proper_subset2_([_e|A], B) :-
    member(_e, B),
    rec_proper_subset2_(A, B).

编辑：

如果你想确保列表没有重复元素，你需要使用list_to_set/2、sort/2或类似的方法。但是这些解决方案也适用于查找子列表。
我认为def_proper_subset/2是一种比较糟糕的解决方案，因为它只能检查A是否是B的子集，但不能在A中生成B的子集。另外两种方法可以实现。

（我搞砸了，忘记包括rec_proper_subset2/2的定义，但现在已经修复了）。