在 Prolog 中保持顺序的同时删除重复项

Question

我正在尝试创建一个从列表中删除重复项同时保持其相对顺序的谓词。例如，列表 [1,2,2,3,4,5,5,2] 应该 return [1,2,3,4,5]。但是，我的代码只能删除连续的重复项，例如，不能删除最后的 2。

remove_duplicates([],[]).
remove_duplicates([H],[H]).
remove_duplicates([H,H|T],[H|List]) :- remove_duplicates(T,List).
remove_duplicates([H,X|T],[H|T1]):- X\=H, remove_duplicates([X|T],T1).

我想到的另一种方法是使用member 来查看Tail 是否包含Head。但是，我能想到的唯一解决方法是，如果头部是尾部的成员，我将移除头部。然而，这将仅保留数字的最后一个实例并破坏列表中数字的相对顺序。

例如：

[1,2,2,3,4,5,5,2] 
[1,3,4,5,2]

当我真正想要的时候

[1,2,3,4,5]

Answer 1

您可以使用累加器：一个额外的参数，这里是一个最初为空的列表，当新元素出现时会增长。传递列表的每个递归调用（或更新的副本）。

例如：

remove_duplicates(LA, LB) :-
    remove_duplicates(LA, LB, <b>[]</b>).

remove_duplicates([], [], <b>_</b>).
remove_duplicates([H|T], R, <b>Seen</b>) :-
    (  member(H, Seen)
    -> (R = S, <b>Seen1 = Seen</b>)
    ;  (R = [H|S], <b>Seen1 = [H|Seen]</b>)
    ),
    remove_duplicates(T, S, <b>Seen1</b>).

这给了我们：

?- remove_duplicates([1,2,2,3,4,5,5,2], L).
L = [1, 2, 3, 4, 5].

当然，您可以使用比列表更有效的数据结构。我把它留作练习。

在 Prolog 中保持顺序的同时删除重复项

Removing Duplicates while maintaining order in Prolog

logic

predicate

list

prolog

duplicates