0

我必须得到两个整数列表（两个纵坐标）之间的列表差异。我把这个白了：

difference(L,[],L) :- !.
difference([],_,[]) :- !.
difference([],[],W). 
difference([H|T1],[D|T2],T3) :- difference(T1,[D|T2],[H|T3]).
difference([H|T1],[H|T2],T3) :- difference(T1,T2,T3).

但为什么我不能得到我的清单差异？如果我写这个：

difference([],[],W):- write(X).

这个例子：

| ?- difference([1,4,4],[1,4],R).    
[4|_27]

它是正确的！注意，如果我有重复的号码，我必须出示！

4

1 回答 1

1

我觉得你的代码很奇怪。例如，您的第三个子句：what's Wfor？好像你的意思是：

difference([],[],_).

第二个问题：在第四个子句中，没有什么可以阻止 H 和 D 成为具有相同绑定的自变量。我怀疑你的意思是这样的：

difference([H|T1],[D|T2],T3) :- H \= D, difference(T1,[D|T2],[H|T3]).

修复这些东西似乎可以修复谓词以给出一个合理的答案：

| ?- difference([1,4,4], [1,4], R).
R = [4]

我认为您的前几个条款试图处理不同类型的基本情况，对吗？例如：

difference(L, [], L)   % handles the case where the second list is exhausted
difference([], _, [])  % handles the case where the first list is exhausted
difference([], [], W)  % handles the case where the lists are exhausted at the same time

这样做的一个问题是 L = [] 是一个合法的绑定，所以第一个和第三个子句的意思是一样的。您可能可以安全地删除第三个，因为它会在第一个上匹配并产生相同的答案。第二个子句更有趣，因为它似乎在说不管我们到目前为止做了什么工作，如果第一个列表为空，则结果为空。我觉得这种可能性有点不和谐——你真的可能想要这两种基本情况吗？：

difference([], L, L).
difference(L, [], L).

我仍然不相信，但是在我更好地了解您要完成的工作之前，我可能无法提供更多帮助。例如，应该发生difference([1, 4], [1, 4, 4], R)什么？我假设你可能想要R = [4]，但你的代码会产生R = []。

另外，我觉得不太可能

difference([],[],W):- write(X).

这将是一个有用的调试策略，因为 Prolog 将为 X 生成一个新的变量绑定，因为它没有任何东西可以引用。

我所有更改的最终版本如下所示：

difference(L, [], L) :- !.
difference([], L, L) :- !.
difference([H|T1], [D|T2], T3) :- D \= H, difference(T1, [D|T2], [H|T3]).
difference([H|T1], [H|T2], T3) :- difference(T1, T2, T3).

编辑：这是否满足您的要求？

not_in1(X, Left, Right) :- member(X, Left), \+ member(X, Right).

not_in(X, Left, Right) :- not_in1(X, Left, Right).
not_in(X, Left, Right) :- not_in1(X, Right, Left).

differences(Left, Right, Differences) :-
    findall(X, not_in(X, Left, Right), Differences).


?- differences([1,2,3,4], [1,3,5], X).
X = [2,4,5]

如果是这样，我会尝试让您的原始代码生成匹配的答案。

编辑2：好的，所以上面解决方案的问题是它是O（N ^ 2）。在最坏的情况下（两个完全不同的列表），它将不得不将列表 1 中的每个项目与列表 2 中的每个项目进行比较。它没有利用两个列表都是有序的这一事实（我相信这就是你所说的“纵坐标”）。

结果看起来更像您的原始代码，但您的原始代码没有利用项目已订购这一事实。这就是为什么第四和第五种情况看起来令人困惑的原因：您应该根据哪个数字更大来递归列表中的一个或另一个。更正后的代码如下所示：

differences([], Result, Result).
differences(Result, [], Result).
differences([H|Ls], [H|Rs], Result) :- differences(Ls, Rs, Result).
differences([L|Ls], [R|Rs], [L|Result]) :-
    L < R,
    differences(Ls, [R|Rs], Result).
differences([L|Ls], [R|Rs], [R|Result]) :-
    L > R,
    differences([L|Ls], Rs, Result).

您可以看到这产生与 O(N^2) 方法相同的结果：

?- differences([1,2,3,4], [1,3,5], X).
X = [2,4,5]

你是对的，你确实需要两种基本情况。这样任何一个列表的其余部分都将成为结果的一部分。大概这些将是最大值（[5]在示例中）。

现在我有三个归纳案例：一个 for <，一个 for>和一个 for =。相等的情况很直观：在两个列表上重复，丢弃两个列表的头部。下一种情况基本上是说如果左头小于右头，则将其添加到结果中并在左尾重复出现。在这种情况下，权利不变。另一个案例是这个案例的镜子。

希望这可以帮助！

于 2013-01-21T20:40:54.367 回答