Prolog no_duplicate 函数

Question

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

% 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，但感谢任何帮助。

Answer 1

回答您的问题：您的解决方案实际上按预期失败了

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)

，这意味着所有与 2 不同的

A

都是解。

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

参见：prolog-dif

Answer 2

这是另一种方法，它之所以有效，是因为

sort/2

删除了重复项：

no_duplicates(L) :-
    length(L, N),
    sort(L, LS),
    length(LS, N).

Answer 3

我会更描述性地讨论这个问题：

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²)？ — 使用

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
  .

Answer 4

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

no_duplicates(L) :-
    \+((nth0(Id1, L, V), nth0(Id2, L, V), Id1 \= Id2)).

Answer 5

Jay 已经注意到您的代码正在运行。另一种方案，稍微简洁一些

no_duplicates(L) :- \+ (append(_, [X|XS], L), memberchk(X, XS)).