没有重复项的反向列表(将其转换为 Set ) -> Prolog

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库，既要纯粹又具有合理的确定性：

?- 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].

swi-prolog中的结果：

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

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

PD_9