4

我正在尝试编写一个简单的程序来检查列表是否有任何重复项。这是我到目前为止所尝试的：

% returns true if the list has no duplicate items.
no_duplicates([X|XS]) :- member(X,XS) -> false ; no_duplicates(XS).
no_duplicates([]) :- true.

如果我尝试no_duplicates([1,2,3,3])。它说的是真的。为什么是这样？我可能在这里误解了 Prolog，但感谢您提供任何帮助。

4

5 回答 5

7

回答您的问题：您的解决方案实际上在no_duplicates([1,2,3,3]). 所以没有问题。

现在进行查询：

?- A = 1, no_duplicates([A, 2]).
A = 1.
?-        no_duplicates([A, 2]), A = 1.

它们的含义相同，因此我们应该期望 Prolog 会产生相同的答案。（更准确地说，我们期望相同的忽略错误和不终止）。

然而，四个提议的解决方案不同！而没有的，则不同：

?- A = 2, no_duplicates([A, 2]).
false.
?-        no_duplicates([A, 2]), A = 2.

请注意，总是第二个查询会造成麻烦。为了解决这个问题，我们需要一个好的答案no_duplicates([A, 2])。它不可能是false，因为有一些值A来使它成为真的。喜欢A = 1。这也不是真的，因为有些值不适合，比如A = 2.

instantiation_error在这种情况下，另一种可能性是发出一个。含义：我没有足够的信息，所以我最好停下来，而不是乱用可能不正确的信息。

理想情况下，我们会得到一个涵盖所有可能解决方案的答案。这个答案dif(A, 2)意味着所有A与 2 不同的都是解决方案。

dif/2是最古老的内置谓词之一，Prolog 0 已经拥有它。不幸的是，后来的发展在 Prolog I 中丢弃了它，因此在爱丁堡 Prolog 和 ISO Prolog 中丢弃了它。

但是，当前的系统包括 SICStus、YAP、SWI 都提供了它。在 ISO-Prolog 中有一种安全的近似方法dif/2

no_duplicates(Xs) :-
   all_different(Xs). % the common name

all_different([]).
all_different([X|Xs]) :-
   maplist(dif(X),Xs).
   all_different(Xs).

请参阅：

于 2014-09-26T10:33:47.070 回答
2

列表中的重复项是不在列表中相同位置的相同元素，因此可以编写 no_duplicates ：

no_duplicates(L) :-
    \+((nth0(Id1, L, V), nth0(Id2, L, V), Id1 \= Id2)).
于 2014-09-25T21:04:33.943 回答
2

我会更描述性地解决这个问题：

no_duplicates( []     ) .  % the empty list is unique
no_duplicates( [X|Xs] ) :- % a list of length 1+ is unique
  \+ member(X,Xs) ,        % - if its head is not found in the tail,
  no_duplicates(Xs)        % - and its tail is itself unique.
  .                        %

考虑到这一点，因为这是一个有点昂贵的操作——O(n 2 )？sort/2- 使用和利用它产生有序集合并删除重复项的事实可能会更有效。你可以说类似

no_duplicates( L ) :-
  sort(L,R)   , % sort the source list, removing duplicates
  length(L,N) , % determine the length of the source list
  length(R,N) . % check that against the result list

或者您可以使用msort/3（它不会删除重复项），也可能会更快一些：

no_duplicates( L ) :-
  msort(L,R),            % order the list
  \+ append(_,[X,X|_],R) % see if we can find two consecutive identical members
  .
于 2014-09-25T21:44:58.207 回答
2

这是另一种方法，它之所以有效，是因为sort/2删除了重复项：

no_duplicates(L) :-
    length(L, N),
    sort(L, LS),
    length(LS, N).
于 2014-09-26T02:13:22.247 回答
1

Jay 已经注意到您的代码正在运行。另一种选择，稍微不那么冗长

no_duplicates(L) :- \+ (append(_, [X|XS], L), memberchk(X, XS)).
于 2014-09-25T22:02:24.653 回答