如何根据 prolog 中的 2 个列表创建索引值列表 [英] How to create a list of index values based on 2 lists in prolog

问题描述

我正在尝试完成一项作业，但是我真的被困在了这一部分.我需要做的是写一个谓词匹配三个参数，所有列表.第三个列表必须包含前两个列表包含相同值的位置的索引.我真的不知道从哪里开始，所以任何帮助将不胜感激！

解决方案

第三个列表必须包含前两个列表包含相同值的位置的索引.

第一点很重要:

<块引用>

第三个列表必须包含前两个列表包含相同值的位置的索引.

使用统一.作为谓词:

same_value(X, X).

<块引用>

第三个列表必须包含前两个列表包含相同值的位置索引.

lists_same_value([X|_], [Y|_]) :- same_value(X, Y).% 成功list_same_value([_|Xs], [_|Ys]) :- % 跳过头list_same_value(Xs, Ys).% 递归定义

在头脑中简化和统一:

lists_same_value([X|_], [X|_]).% 成功list_same_value([_|Xs], [_|Ys]) :- % 跳过头部元素list_same_value(Xs, Ys).% 递归定义

<块引用>

第三个列表必须包含前两个列表包含相同值的位置的索引.

为当前索引添加累加器，当头部相同元素时成功，并查看列表的其余部分.

lists_same_value_index([X|_], [X|_], N, N).% 成功list_same_value_index([_|Xs], [_|Ys], N0, N) :- % 跳过头元素succ(N0, N1), % 下一个索引list_same_value_index(Xs, Ys, N1, N).% 递归定义

实例化累加器:

lists_same_value_index(Xs, Ys, N) :-list_same_value_index(Xs, Ys, 0, N).

与 bagof 一起使用以找到所有解决方案:

?- bagof(N,lists_same_value_index([a,b,c,a,c,d,c], [a,c,c,a,d,d,c], N), Ns).Ns = [0, 2, 3, 5, 6].

<小时>

当然这和两个nth0的解决方案不一样，见:

?- numlist(1, 100, L), time( bagof(N, lists_same_value_index(L, L, N), Ns) ).% 314 推理，0.000 秒内 0.000 CPU(98% CPU，1785481 唇)L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].?- numlist(1, 100000, L), time( bagof(N,lists_same_value_index(L, L, N), Ns) ).% 300,014 次推理，0.052 秒内 0.052 CPU(100% CPU，5765387 唇)L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].

然后用 nth0:

?- numlist(1, 100, L), time( findall(N, ( nth0(N, L, E), nth0(N, L, E) ), Ns) ).% 2,181 次推理，0.001 秒内 0.001 CPU(100% CPU，3329847 唇)L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].?- numlist(1, 100000, L), time( findall(N, ( nth0(N, L, E), nth0(N, L, E) ), Ns) ).% 1,667,166,681 推理，151.244 秒内 151.139 CPU(100% CPU，11030703 唇)L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].

I'm trying to work on an assignment, however am really stuck on this section. What I need to do is write a predicate called matching with three parameters, all lists. The third list must contain the index of the positions in which the first two lists contain the same value. I really don't know where to start on this so any help would be much appreciated!

解决方案

The third list must contain the index of the positions in which the first two lists contain the same value.

First important:

The third list must contain the index of the positions in which the first two lists contain the same value.

Use unification. As predicate:

same_value(X, X).

The third list must contain the index of the positions in which the first two lists contain the same value.

lists_same_value([X|_], [Y|_]) :- same_value(X, Y). % succeed
lists_same_value([_|Xs], [_|Ys]) :-                 % skip head
    lists_same_value(Xs, Ys).                       % recursive definition

Simplify and unify in head:

lists_same_value([X|_], [X|_]).     % succeed
lists_same_value([_|Xs], [_|Ys]) :- % skip head element
    lists_same_value(Xs, Ys).       % recursive definition

The third list must contain the index of the positions in which the first two lists contain the same value.

Add accumulator for current index, succeed when heads are same element, and look in rest of list.

lists_same_value_index([X|_], [X|_], N, N).      % succeed
lists_same_value_index([_|Xs], [_|Ys], N0, N) :- % skip head element
    succ(N0, N1),                                % next index
    lists_same_value_index(Xs, Ys, N1, N).       % recursive definition

Instantiate accumulator:

lists_same_value_index(Xs, Ys, N) :-
    lists_same_value_index(Xs, Ys, 0, N).

Use it with bagof to find all solutions:

?- bagof(N, lists_same_value_index([a,b,c,a,c,d,c], [a,c,c,a,d,d,c], N), Ns).
Ns = [0, 2, 3, 5, 6].

---

and no this is not the same as the solution with the two nth0 of course, see:

?- numlist(1, 100, L), time( bagof(N, lists_same_value_index(L, L, N), Ns) ).
% 314 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1785481 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].

?- numlist(1, 100000, L), time( bagof(N, lists_same_value_index(L, L, N), Ns) ).
% 300,014 inferences, 0.052 CPU in 0.052 seconds (100% CPU, 5765387 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].

and then with nth0:

?- numlist(1, 100, L), time( findall(N, ( nth0(N, L, E), nth0(N, L, E) ), Ns) ).
% 2,181 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 3329847 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].

?- numlist(1, 100000, L), time( findall(N, ( nth0(N, L, E), nth0(N, L, E) ), Ns) ).
% 1,667,166,681 inferences, 151.139 CPU in 151.244 seconds (100% CPU, 11030703 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].

这篇关于如何根据 prolog 中的 2 个列表创建索引值列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！