Prolog:第一个重复值

问题描述 投票:5回答:4

我需要在列表中找到第一个重复值。

prep(3,[1,3,5,3,5]).应该是真的。

prep(5,[1,3,5,3,5]).应该是假的。

我想检查与当前值和先前列表成员的相等性,直到我找到重复,如果它找到一个它将测试与X的相等但我不知道如何在Prolog中做到这一点!

我感谢任何帮助!谢谢

list prolog prolog-dif
4个回答
6
投票

这是一个使用dif/2的纯版本,它实现了声音不等式。 dif/2由B-Prolog,YAP-Prolog,SICStus-Prolog和SWI-Prolog提供。

firstdup(E, [E|L]) :-
    member(E, L).
firstdup(E, [N|L]) :-
    non_member(N, L),
    firstdup(E, L).

member(E, [E|_L]).
member(E, [_X|L]) :-
    member(E, L).

non_member(_E, []).
non_member(E, [F|Fs]) :-
    dif(E, F),
    non_member(E, Fs).

优点是它也可以用于更一般的查询:

?- firstdup(E, [A,B,C]).
E = A, A = B ;
E = A, A = C ;
E = C,
B = C,
dif(A, C) ;
false.

在这里,我们得到三个答案:A是前两个答案中的副本,但有两个不同的理由:A可能等于BC。在第三个答案中,B是副本,但如果CA不同,它将只是重复。

要理解这个定义,请阅读:-作为箭头←所以右边的是你所知道的,左边是你得出的结论。在这方面读取谓词通常在开始时有点恼火,毕竟你可能会想要遵循“执行的线程”。但通常这个线索无处可去 - 它变得太复杂而无法理解。

第一条规则如下:

Provided E is an element of list L we conclude that [E|L] has E as first duplicate.

第二条规则如下:

Provided E is the first duplicate of L (don't panic here and say we don't know that ...) and provided that N is not an element of L we conclude that [N|L] has E as first duplicate.

member/2谓词在许多Prolog系统中提供,non_member(X,L)可以定义为maplist(dif(X),L)。因此,人们会将firstdup/2定义为:

firstdup(E, [E|L]) :-
    member(E, L).
firstdup(E, [N|L]) :-
    maplist(dif(N), L),
    firstdup(E, L).

4
投票

在这个答案中,我们改进了this earlier answer中提供的逻辑纯代码。一步步:

  1. 我们将两个谓词memberd/2non_member/2组合成一个memberd_t/3,它使用一个额外的参数将列表成员资格统一为真值(truefalse)。 memberd_t/3相当于memberd/2 + non_member/2,所以我们可以这样定义: memberd_t(X,Xs,true): - memberd(X,Xs)。 memberd_t(X,Xs,false): - non_member(X,Xs)。 或者,反之亦然,我们可以像这样定义memberd/2non_member/2: memberd(X,Xs): - memberd_t(X,Xs,true)。 non_member(X,Xs): - memberd_t(X,Xs,false)。 在实践中,我们使用memberd_t/3-one的调整实现,具有更好的确定性。 让我们看看memberd_t/3实际上涵盖了memberd/2non_member/2! ? - memberd_t(X,[1,2,3],T)。 T =真,X = 1; T =真,X = 2; T =真,X = 3; T =假,dif(X,1),dif(X,2),dif(X,3)。
  2. 以谓词firstdup/2defined earlier)的以下变体为出发点: firstdup(E,[X | Xs]): - (memberd(X,Xs),E = X; non_member(X,Xs),firstdup(E,Xs))。
  3. 让我们用memberd/2替换non_member/2memberd_t/3的用法! firstdup(E,[X | Xs]): - (memberd_t(X,Xs,true),E = X; memberd_t(X,Xs,false),firstdup(E,Xs))。
  4. 让我们提升memberd_t/3! firstdup(E,[X | Xs]): - memberd_t(X,Xs,T),(T = true - > E = X; T = false,firstdup(E,Xs))。
  5. 上面的模式pred_t(OtherArgs,T), (T = true -> Then ; T = false, Else)可以用if_/3更简洁地表达,写if_(pred_t(OtherArgs),Then,Else)。 firstdup(E,[X | Xs]): - if_(memberd_t(X,Xs),E = X,firstdup(E,Xs))。

让我们运行一些查询!

?- firstdup(1,[1,2,3,1]).
true.                                % succeeds deterministically

?- firstdup(X,[1,2,3,1]).
X = 1.                               % succeeds deterministically

?- firstdup(X,[A,B,C]).              % succeeds, leaving behind a choicepoint
      A=X ,     B=X                  % ... to preserve the full solution set.
;     A=X , dif(B,X), C=X
; dif(A,X),     B=X , C=X
; false.

0
投票

rep(N,List): - 追加(L1,[N | _],List),追加(_,[N | _],L1),\ +(rep(_,L1))。


0
投票

不确定这是否是作业/对你可以使用哪些谓词有限制,但这可以为你做递归。

它说..找到所有重复,即。其中有一个带有列表索引I1的项目,另一个带有I2,这样它们都具有相同的值N,并且索引也不相同。即不要将相同的列表项视为重复项。

在列表AllDups中放置这些重复项(按照从一开始就找到的顺序),如果找到的第一个重复项与您正在检查的值M结合,则谓词为true。

第一次尝试:这有效,但效率非常低,构建了所有重复项的列表

prep(M, List) :-
    findall(N,
        (nth0(I1, List, N),
        nth0(I2, List, N),
        not(I1 =:= I2)),
        AllDups),
    nth1(1, AllDups, M).


?- prep(3,[1,3,5,3,5]).
true.

?- prep(5,[1,3,5,3,5]).
false.

即使您不被允许使用findall,它也可能帮助您找出如何“手动”进行操作。

第二次尝试:这不起作用/回溯太远会产生误报

您甚至可以在没有findall的情况下执行此操作 - 使用nth0查找第一个重复项,然后如果它与您正在检查的值结合,则返回true,否则返回false。

prep(N, List) :-
        nth0(I1, List, N),
        nth0(I2, List, N),
        not(I1 =:= I2).

第三次尝试:这有效,并在找到第一个副本后立即返回

prep(M, List) :-
        nth0(I1, List, N),
        nth0(I2, List, N),
        not(I1 =:= I2), !,
        M == N.
© www.soinside.com 2019 - 2024. All rights reserved.