当前位置： 文江博客 话题详情

Prolog：如何在不更改元素的顺序的情况下消除元素列表的重复项？

发布于 2025-02-09 15:58:15 字数 961 浏览 3 评论 0 原文

作为初学者，我正在尝试从列表中删除所有重复项。 我确实得到一个令人满意的答案，但这应该是唯一的答案。反而， Prolog继续提供其他答案。

我尝试使下面的代码与示例查询 compress（[[a，a，b，c]，s）。 唯一的答案应该是s = [a，b，c]， 我没有获得免费变量的无限解决方案：

S = [a, b, c|_1422]
S = [a, b, _1420, c|_1428]
S = [a, b, _1420, _1426, c|_1434]
S = [a, b, _1420, _1426, _1432, c|_1440].

如下面的代码中所示， 我尝试了剪切。这不是家庭作业问题，我真的只是尝试得到它。特别是，我想知道如何使此特定的代码工作而不是查找某人代码（我知道应该有更多稀疏的解决方案）。先感谢您！！！

compress([],[]).
compress([],_):-!. 
% I tried out a first cut here, but it doesn´t affect the amount of solutions
   
compress([Head|Tail],Set):-
    unique2(Head,Tail,Set),
    compress(Tail,Set).

unique2(X,[],[_List]):-!.  
% I tried out a second cut here, but again there is an endless amount of answers
unique2(X,List,List):-
     member(X,List).
unique2(X,List,List2):-
     member(X,List2).
unique2(X,List,NewList):-
    not(member(X,NewList)),
    addelem(X,List,NewList).

addelem(X,List,[X|List]).
原文

Being a beginner to prolog, I am trying to remove all duplicates from a list.
I do get a satisfying answer but this should be the only answer. Instead,
prolog keeps on providing other answers.

I try to make the code below working with the example query compress([a,a,b,c],S).
The only answer should be S = [a, b, c],
instead of getting an infinite amount of solutions with free variables:

S = [a, b, c|_1422]
S = [a, b, _1420, c|_1428]
S = [a, b, _1420, _1426, c|_1434]
S = [a, b, _1420, _1426, _1432, c|_1440].

I tried cuts, as illustrated in the code below. It is not a homework problem, I just really try to get it. Especially, I would like to know how I can get this specific code working instead of looking up someone elses code (I am aware that there should be way more sparse solutions). Thank you in advance!!!

compress([],[]).
compress([],_):-!. 
% I tried out a first cut here, but it doesn´t affect the amount of solutions
   
compress([Head|Tail],Set):-
    unique2(Head,Tail,Set),
    compress(Tail,Set).

unique2(X,[],[_List]):-!.  
% I tried out a second cut here, but again there is an endless amount of answers
unique2(X,List,List):-
     member(X,List).
unique2(X,List,List2):-
     member(X,List2).
unique2(X,List,NewList):-
    not(member(X,NewList)),
    addelem(X,List,NewList).

addelem(X,List,[X|List]).

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（4）

南笙 2025-02-16 15:58:15

编辑要注意：
从您的评论中：

unique2应该检测列表中的元素是否已经存在于newlist中（即唯一2的第三个参数）。如果不是，则应将其添加到新列表中。如果已经存在的话，它不应（如unique2（x，list，list2）中： - 成员（x，list2）。）list2保持不变。唯一2的第二子句从压缩中调用unique2（头部，尾部，设置）后使用，我现在看到它存在一个巨大的问题：仅重复头部。当同一元素稍后或发生另一个元素发生两次或更多时（例如，压缩（[a，a，b，b，c]，s）。

我认为您正在考虑您的 unique2 谓词。

您的 unique2 只需要这样做：

try_add( H , T ,    S  , S  ) :- member(H,T), !.
try_add( H , _ , [H|S] , S  ) .

compress/2 需要处理终止案例（空列表）。一旦这样做，就已经得到了： .org/p/sypssqlo.pl 

compress( []          , []  ) .
compress( [Head|Tail] , Set ):-
    try_add(Head,Tail,Set, NextSet),
    compress(Tail,NextSet)
    .

try_add( H , T ,    S  , S  ) :- member(H,T), !.
try_add( H , _ , [H|S] , S  ) .

[现在，返回原始答案]

这将丢弃所有重复项的最后一个：

https://swish.swim.swi-prolog.org/p/mghqgthb.pl 

dedupe( []    ,    []  ) .
dedupe( [H|T] ,    Xs  ) :- member(H,T), !, dedupe(T,Xs).
dedupe( [H|T] , [H|Xs] ) :-                 dedupe(T,Xs).

保持第一个并不复杂。我们将只使用累加器的辅助谓词。由于它以相反的顺序构建结果集，因此我们需要逆转它。这给了我们这一点：

dedupe( Xs, Ys ) :- dedupe(Xs,[],Rs) , reverse(Rs,Ys).

dedupe( []    , Ys , Ys ) .
dedupe( [H|T] , Ts , Ys ) :- member(H,Ts), !, dedupe(T,Ts,Ys).
dedupe( [H|T] , Ts , Ys ) :-                  dedupe(T,[H|Ts],Ys).

Edited to note:
From your comment:

unique2 should detect if an element from List is already present in NewList (i.e. third argument of unique2). If it is not, it should be added to the new List. If it is already, it should not (as in unique2(X,List,List2):- member(X,List2).) where List2 stays the same. The second clause of unique2 is used after calling unique2(Head,Tail,Set) from within compress and I see now that there is a huge problem with it: the head only is not immediately repeated. When the same element occurs later or when another element occurs twice or more (e.g. compress([a,a,b,b,c],S).) the duplicates stay.

I think that you're overthinking youro unique2 predicate.

Your unique2 just need do something like this:

try_add( H , T ,    S  , S  ) :- member(H,T), !.
try_add( H , _ , [H|S] , S  ) .

And your compress/2 needs to handle the terminating case (the empty list). Once you do that, you've got this: https://swish.swi-prolog.org/p/sypssqLO.pl

compress( []          , []  ) .
compress( [Head|Tail] , Set ):-
    try_add(Head,Tail,Set, NextSet),
    compress(Tail,NextSet)
    .

try_add( H , T ,    S  , S  ) :- member(H,T), !.
try_add( H , _ , [H|S] , S  ) .

[and now, back to the original answer]

This will discard all but the last of any duplicates:

https://swish.swi-prolog.org/p/MghqGThB.pl

dedupe( []    ,    []  ) .
dedupe( [H|T] ,    Xs  ) :- member(H,T), !, dedupe(T,Xs).
dedupe( [H|T] , [H|Xs] ) :-                 dedupe(T,Xs).

To keep the first isn't much more complicated. We'll just use a helper predicate with an accumulator. Since it builds the result set in reverse order, we need to reverse it. That gives us this:

https://swish.swi-prolog.org/p/PHQgypMu.pl

dedupe( Xs, Ys ) :- dedupe(Xs,[],Rs) , reverse(Rs,Ys).

dedupe( []    , Ys , Ys ) .
dedupe( [H|T] , Ts , Ys ) :- member(H,Ts), !, dedupe(T,Ts,Ys).
dedupe( [H|T] , Ts , Ys ) :-                  dedupe(T,[H|Ts],Ys).
回复 原文
娇纵 2025-02-16 15:58:15

这是一种无需反向的方法，它似乎比 dedupe （均使用 MemberChk 进行性能，这是在SWI-Prolog中进行了优化的） ：

remove_duplicate_elems([], []).
remove_duplicate_elems([H|T], [H|Uniqs]) :-
    % Seed Seen with H
    remove_duplicate_elems_(T, [H], Uniqs).

remove_duplicate_elems_([], _, []).
remove_duplicate_elems_([H|T], Seen, Uniqs) :-
    memberchk(H, Seen), !,
    remove_duplicate_elems_(T, Seen, Uniqs).
remove_duplicate_elems_([H|T], Seen, [H|Uniqs]) :-
    remove_duplicate_elems_(T, [H|Seen], Uniqs).

SWI-Promog中的性能比较：

?- numlist(1, 10_000, NL1), numlist(1, 10_000, NL2),
numlist(1, 10_000, NL3), append([NL1, NL2, NL3], L),
time(remove_duplicate_elems(L, LU)), length(LU, LULen).
% 89,999 inferences, 2.324 CPU in 2.327 seconds (100% CPU, 38726 Lips)

?- numlist(1, 10_000, NL1), numlist(1, 10_000, NL2),
numlist(1, 10_000, NL3), append([NL1, NL2, NL3], L),
time(dedupe(L, LU)), length(LU, LULen).
% 100,004 inferences, 2.414 CPU in 2.417 seconds (100% CPU, 41424 Lips)

Here is a method without needing reverse which seems a little faster than dedupe (both using memberchk for performance, which is optimized in swi-prolog):

remove_duplicate_elems([], []).
remove_duplicate_elems([H|T], [H|Uniqs]) :-
    % Seed Seen with H
    remove_duplicate_elems_(T, [H], Uniqs).

remove_duplicate_elems_([], _, []).
remove_duplicate_elems_([H|T], Seen, Uniqs) :-
    memberchk(H, Seen), !,
    remove_duplicate_elems_(T, Seen, Uniqs).
remove_duplicate_elems_([H|T], Seen, [H|Uniqs]) :-
    remove_duplicate_elems_(T, [H|Seen], Uniqs).

Performance comparison in swi-prolog:

?- numlist(1, 10_000, NL1), numlist(1, 10_000, NL2),
numlist(1, 10_000, NL3), append([NL1, NL2, NL3], L),
time(remove_duplicate_elems(L, LU)), length(LU, LULen).
% 89,999 inferences, 2.324 CPU in 2.327 seconds (100% CPU, 38726 Lips)

?- numlist(1, 10_000, NL1), numlist(1, 10_000, NL2),
numlist(1, 10_000, NL3), append([NL1, NL2, NL3], L),
time(dedupe(L, LU)), length(LU, LULen).
% 100,004 inferences, 2.414 CPU in 2.417 seconds (100% CPU, 41424 Lips)
回复 原文
太阳公公是暖光 2025-02-16 15:58:15

我想到了：

remove_duplicate_elems([], []).
remove_duplicate_elems([H|T], [H|Clean]) :-
    remove_elem_all(T, H, Clean1),
    remove_duplicate_elems(Clean1, Clean).

remove_elem_all([], _, []).
remove_elem_all([H|T], E, L) :-
    % Discard duplicate
    (   H == E -> L = L0
    ;   L = [H|L0]
    ),
    remove_elem_all(T, E, L0).

...但是它比 dedupe ：

?- numlist(1, 3_000, NL1), numlist(1, 3_000, NL2),
numlist(1, 3_000, NL3), append([NL1, NL2, NL3], L),
time(remove_duplicate_elems(L, LU)), length(LU, LULen).
% 13,507,501 inferences, 1.531 CPU in 1.513 seconds (101% CPU, 8823982 Lips)

?- numlist(1, 3_000, NL1), numlist(1, 3_000, NL2),
numlist(1, 3_000, NL3), append([NL1, NL2, NL3], L),
time(dedupe(L, LU)), length(LU, LULen).
% 13,522,504 inferences, 1.260 CPU in 1.245 seconds (101% CPU, 10730775 Lips)

使用 memberchk 而不是成员 in dedupe ，在Swi-Prolog中的性能加倍：

?- numlist(1, 3_000, NL1), numlist(1, 3_000, NL2),
numlist(1, 3_000, NL3), append([NL1, NL2, NL3], L),
time(dedupe(L, LU)), length(LU, LULen).
% 30,004 inferences, 0.682 CPU in 0.674 seconds (101% CPU, 43994 Lips)

I came up with:

remove_duplicate_elems([], []).
remove_duplicate_elems([H|T], [H|Clean]) :-
    remove_elem_all(T, H, Clean1),
    remove_duplicate_elems(Clean1, Clean).

remove_elem_all([], _, []).
remove_elem_all([H|T], E, L) :-
    % Discard duplicate
    (   H == E -> L = L0
    ;   L = [H|L0]
    ),
    remove_elem_all(T, E, L0).

... but it is slower than dedupe:

?- numlist(1, 3_000, NL1), numlist(1, 3_000, NL2),
numlist(1, 3_000, NL3), append([NL1, NL2, NL3], L),
time(remove_duplicate_elems(L, LU)), length(LU, LULen).
% 13,507,501 inferences, 1.531 CPU in 1.513 seconds (101% CPU, 8823982 Lips)

?- numlist(1, 3_000, NL1), numlist(1, 3_000, NL2),
numlist(1, 3_000, NL3), append([NL1, NL2, NL3], L),
time(dedupe(L, LU)), length(LU, LULen).
% 13,522,504 inferences, 1.260 CPU in 1.245 seconds (101% CPU, 10730775 Lips)

Using memberchk instead of member in dedupe, doubles the performance in swi-prolog:

?- numlist(1, 3_000, NL1), numlist(1, 3_000, NL2),
numlist(1, 3_000, NL3), append([NL1, NL2, NL3], L),
time(dedupe(L, LU)), length(LU, LULen).
% 30,004 inferences, 0.682 CPU in 0.674 seconds (101% CPU, 43994 Lips)
回复 原文
溺ぐ爱和你が 2025-02-16 15:58:15

实现这一目标的一种有趣的方法

nub(L,R):- maplist( flip(memberchk,R), L), length(R,_), !.

flip(P,A,B) :- G =.. [P,B,A], G.

A fun way to achieve this is with

nub(L,R):- maplist( flip(memberchk,R), L), length(R,_), !.

flip(P,A,B) :- G =.. [P,B,A], G.
回复 原文
~没有更多了~

关于作者

药祭#氼

暂无简介

文章
评论
28 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

櫻之舞

文章 0 评论 0

弥枳

文章 0 评论 0

m2429

文章 0 评论 0

寻找一个思念的角度

文章 0 评论 0

野却迷人

文章 0 评论 0

我怀念的。

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文