反转没有重复项的列表（将其转换为集合）->序言

Question

我需要从列表中删除所有重复项，然后以相反的顺序显示它。

到目前为止我有这个：

reverseInSet([], Y,R):-
 R=Y.

reverseInSet([H|T], Y, R):- 
 removeElement(H,T,T1), 
 reverseInSet(T1, [H|Y], R).


removeElement(_,[],[]).    

removeElement(X,[X|T],L):-    
 removeElement(X,T,L).

removeElement(X,[Y|T],L):-   
 removeElement(X,T,L1),
 L=[Y|L1].

输出是这样的：

reverseInSet([1,2,3,3,9,3],[],P).
P = [9, 3, 2, 1]
P = [3, 9, 3, 2, 1]
P = [9, 3, 3, 2, 1]
P = [9, 3, 3, 2, 1]
P = [3, 9, 3, 3, 2, 1]

有什么想法吗？

Answer 1

这是最简单的方法。如果源列表中存在重复条目，则保留最后一个此类条目，并丢弃其前面的条目。

list_to_set_reverse( Xs, Ys ) :- list_to_set( Xs, Zs ) , reverse(Zs,Ys) .

list_to_set( []     , []     ) .
list_to_set( [X|Xs] , Ys     ) :- member(X,Xs), !, list_to_set(Xs,Ys) .
list_to_set( [X|Xs] , [X|Ys] ) :-                  list_to_set(Xs,Ys) .

您也可以一次完成。您只需要使用累加器以相反的顺序构建结果列表：

list_to_set_reverse( Xs, Ys ) :- list_to_set( Xs, [], Ys ) .

list_to_set( []     , Ys , Ys ) .
list_to_set( [X|Xs] , Ts , Ys ) :- member(X,Xs), !, list_to_set(Xs,Ts,Ys) .
list_to_set( [X|Xs] , Ts , Ys ) :-                  list_to_set(Xs,[X|Ts],Ys) .

这也会保留源列表中的最后一个重复项。但是，由于我们在这里使用累加器来构建结果列表，因此很容易重新调整它以保留任何重复项中的第一个：我们只需检查候选项是否已在结果集中（而不是而不是检查它是否稍后出现在源列表中）。

list_to_set_reverse( Xs, Ys ) :- list_to_set( Xs, [], Ys ) .

list_to_set( []     , Ys , Ys ) .
list_to_set( [X|Xs] , Ts , Ys ) :- member(X,Ts), !, list_to_set(Xs,Ts,Ys).
list_to_set( [X|Xs] , Ts , Ys ) :-                  list_to_set(Xs,[X|Ts],Ys) .

Answer 2

使用 reif 库，既纯粹又合理确定：

:- use_module(library(reif)).

reverse_without_duplicates(Lst, LstRevDeDup) :-
    reverse_without_duplicates_(Lst, [], LstRevDeDup).


reverse_without_duplicates_([], Lst, Lst).

reverse_without_duplicates_([H|T], Upto, LstRevDeDup) :-
    memberd_t(H, T, Bool),
    reverse_without_duplicates_bool_(Bool, T, H, Upto, LstRevDeDup).

reverse_without_duplicates_bool_(true, T, _H, Upto, LstRevDeDup) :-
    reverse_without_duplicates_(T, Upto, LstRevDeDup).
reverse_without_duplicates_bool_(false, T, H, Upto, LstRevDeDup) :-
    % Include head
    reverse_without_duplicates_(T, [H|Upto], LstRevDeDup).

结果swi-prolog：

?- time(reverse_without_duplicates([1, 2, 3, 3, 9, 3], X)).
% 52 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 1025277 Lips)
X = [3,9,2,1].

这种纯粹的方法显示了合理的答案：

?- time(reverse_without_duplicates([1, 2, N, 3, 9, 3], L)).
% 49 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 1030603 Lips)
N = 1,
L = [3,9,1,2] ;
% 127 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 845646 Lips)
N = 2,
L = [3,9,2,1] ;
% 152 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1051910 Lips)
N = 3,
L = [3,9,2,1] ;
% 178 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1229859 Lips)
N = 9,
L = [3,9,2,1] ;
% 88 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 648633 Lips)
L = [3,9,N,2,1],
dif(N,1),
dif(N,9),
dif(N,3),
dif(N,2).