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).
4

1 回答 1

2

如果我理解正确，您上次尝试中的前两个声明意味着，具有1 个元素的列表都是空列表的真子集（假），而空列表是具有一个元素的列表的真子集（真的）; 第一个应该是有问题的，因为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，但我现在已经修复了它）。

于 2013-10-24T21:11:32.503 回答