如何从SWI-Prolog中的列表中删除重复项？

Question

所以我需要编写一个谓词remove_duplicates/2来删除给定列表中的重复元素.例如:

?- remove_duplicates([a,a,b,c,c], List). List = [a,b,c] Yes

请记住,我只学习SWI-Prolog两天,只了解Prolog的基础知识.这就是我现在所拥有的:

remove_duplicates([H | T], List) :- member(H, T), append(T, [], List1).

这适用于列表,[a,a,b,c]但不适用于尾部中两个元素相同的列表.我想我不得不将Head删除到临时列表,创建一个新的Head并重复谓词.我不知道该怎么做.此外,当Head不在尾部时,例如列表之类的[a,b,b,c,],终端只是说False,因为member(H, T)不是真的.

有任何想法吗？

Answer 1

要删除重复项,如果订单无关紧要,最简单的方法是使用sort/2:

?- sort([a,a,b,b,c], X).
X = [a, b, c].

?- sort([c,c,a,a,b], X).
X = [a, b, c].

当然,您会看到元素的原始顺序丢失了.更重要的是,如果您正在排序的列表已经基础(其中没有自由变量),这只能保证正确.考虑这个小例子:

?- sort([X,Y], [a,a]).
X = Y, Y = a.

如果您的目标是删除重复项,感觉不完全正确....

所以你不妨写一下:

must_be(ground, List), sort(List, Unique).

您也可以自己完成,并保留原始订单.但是,你需要记录你到目前为止看到的元素.例如,您可以将它们保存在一个额外的列表中:

到目前为止看到的元素列表在开头是空的

list_unique(List, Unique) :-
    list_unique_1(List, [], Us).

list_unique_1([], _, []).
list_unique_1([X|Xs], So_far, Us) :-
    list_unique_2(X, Xs, So_far, Us).

如果到目前为止看到的所有元素都与X不同,请将其放入唯一元素列表中,并将其添加到目前为止看到的元素列表中.

list_unique_2(X, Xs, So_far, [X|Us]) :-
    maplist(dif(X), So_far),
    list_unique_1(Xs, [X|So_far], Us).

如果到目前为止已经看到该元素,则跳过它.

list_unique_2(X, Xs, So_far, Us) :-
    memberchk(X, So_far),
    list_unique_1(Xs, So_far, Us).

这是最直接的方式.还有其他更聪明的方法可能会有更好的复杂性,但这是最容易编写的.

Answer 2

一个简单而漂亮的删除重复项的代码是：

remove_duplicates([], []).

remove_duplicates([Head | Tail], Result) :-
    member(Head, Tail), !,
    remove_duplicates(Tail, Result).

remove_duplicates([Head | Tail], [Head | Result]) :-
    remove_duplicates(Tail, Result).

正如Ulle Endriss 的《Prolog 简介》中所述

Answer 3

你的谓词有几个问题：

remove_duplicates([H | T], List) :-
  member(H, T),
  append(T, [], List1).

首先你应该有一个递归谓词，你检查列表的头部，但你不递归地检查列表的尾部：

所以你可以把它改成：

remove_duplicates([H | T], List) :- 
      member(H, T),
      remove_duplicates( T, List).

以上递归调用尾部。

其次，您必须决定如果 h 不是列表成员会发生什么，因此您需要添加另一个子句：

remove_duplicates([H | T], [H|T1]) :- 
       \+member(H, T), 
       remove_duplicates( T, T1).

上面检查 H 是否存在于 T 中，如果不存在，则强制您要返回的列表的第一个元素为元素 H：

如果这不是那么清楚，上面等于这个：

  remove_duplicates([H | T], List) :- 
           \+member(H, T), 
           List=[Head|Tail],
           Head=H,
           remove_duplicates( T, Tail).

这不是很优雅，只是为了了解以前的工作原理。

最后，您需要一个空列表的递归基础：

remove_duplicates([],[]).

所以根据上述子句的谓词remove_duplicates应该是：

remove_duplicates([],[]).

remove_duplicates([H | T], List) :-    
     member(H, T),
     remove_duplicates( T, List).

remove_duplicates([H | T], [H|T1]) :- 
      \+member(H, T),
      remove_duplicates( T, T1).

尽管您必须注意上面的每个元素只会保留一次，例如：

remove_duplicates([a,a,b,c],L).
L = [a, b, c] ;
false.

这没问题，但请查看下面的示例：

remove_duplicates([a,a,b,a,c],L).
L = [b, a, c] ;
L = [b, a, c] ;
false.

这将返回 L=[b,a,c] 因为它删除了列表的前两个 'a' 而只保留了第三个。

如果您只想删除重复项，由于成员谓词，上述方法将不起作用。你可以写：

remove_duplicates2([],[]).

remove_duplicates2([H],[H]).

remove_duplicates2([H ,H| T], List) :-remove_duplicates( [H|T], List).

remove_duplicates2([H,Y | T], [H|T1]):- Y \= H,remove_duplicates( [Y|T], T1).

谓词 remove_duplicates2 类似于 remove_duplicates，但有一些重要的区别：

1）您不使用成员，但是您检查当您有一个包含两个相同元素的列表 [H,H|T] 并且只保留一个时会发生什么，因此您忽略第一个 H 并递归调用 remove_duplicates2([H| T],L)。

2）如果你输入了 [H,Y|T]（一个至少有两个元素 H,Y 和列表尾部的列表）并且 H\=Y 你调用 remove_duplicates2([Y|T],T1) 并且你已将 H 存储到要返回的列表中。

3) 最后，因为 all 子句需要至少两个元素，所以递归的基础是具有一个元素的列表：remove_duplicates2([H],[H])。

4) 子句 remove_duplicates2([],[])。仅在输入为空列表时使用，因此需要覆盖此输入。

remove_duplicates2 谓词会给你：

 remove_duplicates2([a,a,b,a,c],L).
L = [a, b, a, c] ;
false.

remove_duplicates2([a,a,b,c],L).
L = [a, b, c] ;
false.