首页 文章

只留下重复元素的一个副本

提问于
浏览
3

我正在尝试在Prolog中创建一个带有列表的谓词,并且只返回列表中相邻重复项的一个副本 . 例如:

?- adj_dups([a,b,a,a,a,c,c],R).
R=[a,c]

我想我需要两个基本情况:

adj_dups([],[]). % if list is empty, return empty list
adj_dups([X],[]). % if list contains only one element, return empty list (no duplicates).

然后对于递归部分,我需要将头部与尾部的头部进行比较,然后递归地在列表的尾部进行 . 这是我到目前为止所提出的,但它不起作用!

adj_dups([X,X|T],[X|R]):- adj_dups([X|T],R). % if the list starts with duplicates
adj_dups([X,Y|T],R):- X \= Y, adj_dups([X|T],R). % if the list doesn't start wih duplicates

我该如何修复它以便获得正确的结果?

编辑:我将列出一些示例,以帮助您了解我的问题 . 代码应该如何表现:

?- adj_dups([a,c,c,c,b],R).
R = [c]
?- adj_dups([a,b,b,a,a],R).
R = [b,a]
?- adj_dups([a,b,b,a],R).
R = [b]

我的代码如何表现:

?- adj_dups([a,c,c,c,b],R).
R = []
?- adj_dups([a,b,b,a,a],R).
R = [a,a]
?- adj_dups([a,b,b,a],R).
R = [a]

谢谢 .

2 回答

  • 0

    我觉得这个规范含糊不清

    只列出相邻副本的一个副本

    因为它没有说明当我们多次出现相同的重复符号时会发生什么 .

    adj_dups([],[]).
    adj_dups([X,X|T],[X|R]) :-
        skip(X,T,S),
        adj_dups(S,R),
        \+ memberchk(X,R),
        !.
    adj_dups([_|T],R) :- adj_dups(T,R).
    
    skip(X,[X|T],S) :- !, skip(X,T,S).
    skip(_,T,T).
    

    这会产生

    ?- adj_dups([a,a,c,c,a,a],R).
    R = [c, a].
    

    评论memberchk行代替

    ?- adj_dups([a,a,c,c,a,a],R).
    R = [a, c, a].
    
  • 1

    让我们来看看当你尝试一个更简单的案例时会发生什么:

    adj_dups([a,b,b,a],R).
    

    前三个谓词不匹配,因此我们得到:

    adj_dups([X,Y|T],R):- X \= Y, adj_dups([X|T],R).
    

    这是有问题的情况:X绑定到a,Y绑定到b .
    然后它将调用 adj_dups([a,b,a],R) ,将T绑定到 [b,a] ,它只有一个b . 实际上,您现在已经从列表中删除了重复的b,然后才能处理它 .

    让我们首先创建一些辅助谓词 - 尤其是从列表中过滤元素的谓词 . 然后,在递归部分,有两种情况:

    如果第一个元素出现在正在处理的列表的尾部,则它是重复的;我们需要返回第一个元素,然后返回已处理的尾部 . 处理尾部包括从中删除第一个元素,然后检查尾部是否有重复 .

    第二种情况要简单得多:如果第一个元素没有出现在尾部,我们只需将 adj_dups 应用于尾部并返回它 . 第一个元素从未重复过,所以我们忘了它 .

    % Filter the element X from a list.
    filter(X,[],[]).
    filter(X,[X|T],R)     :- filter(X,T,R).
    filter(X,[Y|T],[Y|R]) :- X \= Y, filter(X,T,R).
    
    % Return "true" if H is NOT a member of the list.
    not_member(H,[]).
    not_member(H,[H|T]):-fail.
    not_member(H,[Y|T]):-H \= Y, not_member(H,T).
    
    
    % Base cases for finding duplicated values.
    adj_dups([],[]).  % if list is empty, return empty list
    adj_dups([X],[]). % if list contains only one element, return empty list (no duplicates).
    
    % if H1 is in T1 then return the H1 followed by the adj_dups of (T1 minus H1).
    % if H1 is not in T1 then return the adj_dups of T1.
    adj_dups([H1|T1],[H1|T3]):-member(H1,T1), filter(H1,T1,T2), adj_dups(T2,T3).
    adj_dups([H1|T1],T3):-not_member(H1, T1), adj_dups(T1,T3).
    

    对于示例输入[a,b,a,a,a,c,c],这给出了输入[a,b,b,a]和R = [a,c]的R = [a,b] .

相关问题