Prolog: 第一个重复值

Question

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

prep(3,[1,3,5,3,5]) 应该返回 true。

prep(5,[1,3,5,3,5]) 应该返回 false。

我考虑通过检查当前值和前面的列表成员是否相等，直到找到重复项，如果找到重复项，则会测试与 X 的相等性，但我不知道如何在 Prolog 中实现这一点！

感谢任何帮助！谢谢

- Zezinho

Answer 1

这里是使用 dif/2 实现声音不等的纯版本。 dif/2 可以在 B-Prolog、YAP-Prolog、SICStus-Prolog 和 SWI-Prolog 中使用。

优点是它还可以与更一般的查询一起使用：

在这里，我们得到了三个答案：A 是前两个答案中的重复项，但有两个不同的原因：A 可能等于 B 或 C。在第三个答案中，B 是重复项，但只有在 C 不同于 A 时才是重复项。

要理解定义，请将 ： 读为箭头 ←。因此，右侧是您知道的内容，左侧是您得出的结论。通常，在开始时，按这种方向阅读谓词有点令人烦恼，毕竟您可能会想要跟随“执行的线程”。但是，通常这个线程会导致无处可去-变得过于复杂而难以理解。

第一条规则读取为：

假设 E 是列表 L 的元素，我们得出 [E|L] 具有 E 作为第一个重复项。

第二条规则读取为：

假设 E 是 L 的第一个重复项（不要惊慌，说我们不知道这个...），并且假设 N 不是 L 的元素，则我们得出 [N|L] 具有 E 作为第一个重复项。

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

- false

---

也许最好将文本的最后一行改为“...并且可以将nonmember(X,L)定义为maplist(dif(X),L)”，以便在那里给出X和L的上下文。 :) - Will Ness

Answer 2

在这个答案中，我们改进了早期答案中展示的逻辑纯代码。步骤如下：

我们将两个谓词memberd/2和non_member/2合并成一个谓词memberd_t/3，它使用一个额外的参数将列表成员关系转化为真值（true或false）。 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/2和non_member/2：

``` memberd(X,Xs) :- memberd_t(X,Xs,true).

non_member(X,Xs) :- memberd_t(X,Xs,false). ```

在实践中，我们使用调整后的memberd_t/3实现——具有更好的确定性。让我们看看memberd_t/3实际上涵盖了memberd/2和non_member/2！

``` ?- memberd_t(X,[1,2,3],T). T = true , X=1 ; T = true , X=2 ; T = true , X=3 ; T = false, dif(X,1), dif(X,2), dif(X,3). ```

接下来，我们以谓词firstdup/2（之前定义过的）的以下变体为起点：

``` firstdup(E,[X|Xs]) :- ( memberd(X,Xs), E=X ; non_member(X,Xs), firstdup(E,Xs) ). ```

让我们用memberd_t/3替换memberd/2和non_member/2！

``` firstdup(E,[X|Xs]) :- ( memberd_t(X,Xs,true), E=X ; memberd_t(X,Xs,false), firstdup(E,Xs) ). ```

然后我们将memberd_t/3提升一级！

``` firstdup(E,[X|Xs]) :- memberd_t(X,Xs,T), ( T=true -> E=X ; T=false, firstdup(E,Xs) ). ```

上述模式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.                                % 成功确定
?- firstdup(X,[1,2,3,1]).
X = 1.                               % 成功确定
?- firstdup(X,[A,B,C]).              % 成功，保留了一个选择点
      A=X ,     B=X                  % ... 以保留完整的解决方案集合。
;     A=X , dif(B,X), C=X
; dif(A,X),     B=X , C=X
; false.

- repeat

Answer 3

rep（N，List）：- append（L1，[N | _]，List），append（_，[N | _]，L1），\ +（rep（_，L1））。

- 尾崎隆大

Answer 4

不确定这是否是作业/是否有限制您可以使用哪些谓词，但这会让Prolog为您执行递归。

它的意思是..查找所有重复项，即具有列表索引I1和另一个具有I2的项目，使得它们都具有相同的值N，并且索引不相同，即不将相同的列表项视为重复项。

这些重复项按照它们被发现的顺序（关键是从开头）放在列表AllDups中，如果第一个找到的重复项与您正在检查的值M一致，则谓词为真。

第一次尝试：这个方法可行，但效率非常低下，会构建一个包含所有重复项的列表

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.

- magus

---

我仍然是Prolog的初学者，这对我来说有点困难理解。我们在课堂上没有学习Prolog，我几乎没有时间自己好好学习它，虽然这个练习只是作为自学而给出的，但我会尝试后面更好地理解它。谢谢你的时间！ :) - Zezinho

@false：I1和I2是列表的索引。即在列表“List”中查找两个具有相同值“N”的列表项，但其索引不同。 - magus

@will ness - 是的 - 我以为我已经测试过了。我已经在上面的编辑2中放置了一个修复版本。我的第一个解决方案非常低效...首先构建了一个所有重复项的列表。编辑2包含一个剪切，以确保在找到两个具有不同索引的匹配值后，如果输入值与找到的值不匹配，它将不会回溯到另一个nth0值。 - magus

嗨，现在看起来应该可以工作了；最好你在你的回答中清楚地说明哪些代码是正常工作的，哪些不是。 - Will Ness

感谢您的要求，已按照要求插入。 - magus