根据prolog中包含索引和原子的另一个列表来改变变量列表。

问题描述 投票：0回答：2

我有一个变量列表 E 和一份名单 L 我想要一个这样的谓词。

E=[A,B,C,D]
L=[(1,b),(3,m)]
solve(E,L).
E=[b,B,m,D]

基本上 solve() 循环往复 L 并改变 E 借用 (a,b) 来统一索引处的变量 a 与原子 B. 有什么方法可以做到这一点吗？

list indexing prolog
2个回答
2
投票

(名字不好听的)的含义 solve/2 谓词是这样的："对于每一对(Index, Element)、 Index-输入列表的第1个元素是 Element". 你可能使用的Prolog实现已经有了一个类似于 nth1/3 其中表达了 "的 Index-的第 List 是 Element". 例如，在SWI-Prolog中。

?- List = [A, B, C, D], nth1(3, List, this_is_the_third_element).
List = [A, B, this_is_the_third_element, D],
C = this_is_the_third_element.

所以你的谓词的另一种实现方式是简单地调用... nth1/3 对于你的每一个(Index, Element)对。

solve(_List, []).
solve(List, [(Index, Elem) | Pairs]) :-
    nth1(Index, List, Elem),
    solve(List, Pairs).

这样你就完成了

?- E = [A, B, C, D], L = [(1, b), (3, m)], solve(E, L).
E = [b, B, m, D],
A = b,
C = m,
L = [(1, b),  (3, m)] ;
false.

请注意，这个解决方案很简单，但它的复杂度是四次方的，因为输入列表的长度。nth1/3 可能需要访问整个N个元素列表N次。在不太可能的情况下，如果你需要这个谓词用于一些大型程序的性能关键部分，可以考虑另一个答案中勾画的更优化的解决方案。

2
投票

有什么办法可以做到这一点吗？

当然有。就像Perl中所说的那样 "有不止一种方法可以做到"

有几个问题。

不要使用 (1,b) 使用成语 -(1,b) 取而代之，写成 1-b 的对子）。这样就可以得到一个对子的列表。L=[1-b,3-m]. 有一个专门处理这种对的库。https:/www.swi-prolog.orgpldocman?section=pairs - 或者你也可以使用AVL树实现的真实地图。https:/www.swi-prolog.orgpldocman?section=assoc

现在你只需要

  1. 对数据对进行排序，可能是用keysort。https:/www.swi-prolog.orgpldocdoc_for?object=sort2 或 https:/www.swi-prolog.orgpldocdoc_for?object=sort4
  2. 从左到右浏览列表，保留当前索引，当排序列表中的下一个键被击中时，执行替换，否则只保留列表中的现有项。结果将作为列表的头部进入一个累加器变量。
  3. 完成! 对越界索引等的特殊处理，要通过抛出或失败来适当处理。

如何通过排序后的对列表（我没有测试这个！）。

% case of Index hit:

go_through([Index-Value|Rest],Index,InList,OutList) :-
   InList  = [I|Rest],
   OutList = [Value|More],
   succ(Index,NextIndex),
   go_through(Rest,NextIndex,Rest,More).

% case of Index miss:

go_through([NotYetIndex-Value|Rest],Index,InList,OutList) :-   
   NotYetIndex > Index,  % that should be the case
   InList  = [I|Rest],
   OutList = [I|More],
   succ(Index,NextIndex),
   go_through(Rest,NextIndex,Rest,More).

go_through([],_,L,L). % DONE

或者，你可以写一个 replace0 在列表中逐一替换索引，并通过在列表中的 L 列表。

补充：使用go_through的工作代码

其实包含了一些小细节

another_vectorial_replace1(ListIn,ReplacePairs,ListOut) :-
   maplist([_,_]>>true,ListIn,ListOut),               % Bonus code: This "makes sure" (i.e. fails if not) 
                                                      % that ListIn and ListOut are the same length
   maplist([(A,B),A-B]>>true,ReplacePairs,RealPairs), % Transform all (1,b) into [1,b]
   maplist([K-_]>>integer(K),RealPairs),              % Make sure the RealPairs all have integers on first place   
   keysort(RealPairs,RealPairsSorted),                % Sorting by key, which are integers; dups are not removed!
   debug(topic,"ListIn: ~q",[ListIn]),
   debug(topic,"RealPairsSorted: ~q",[RealPairsSorted]),
   go_through(RealPairsSorted,1,ListIn,ListOut),
   debug(topic,"ListOut: ~q",[ListOut]).

% Case of Index hit, CurIndex is found in the first "Replacement Pair"

go_through([CurIndex-Value|RestPairs],CurIndex,ListIn,ListOut) :-
   !, % Commit to choice
   ListIn  = [_|Rest],
   ListOut = [Value|More],
   succ(CurIndex,NextIndex),
   go_through(RestPairs,NextIndex,Rest,More).

% Case of Index miss:

go_through([NotYetIndex-V|RestPairs],CurIndex,ListIn,ListOut) :-
   NotYetIndex > CurIndex,  % that should be the case because of sorting; fail if not
   !, % Commit to choice
   ListIn  = [X|Rest],
   ListOut = [X|More],
   succ(CurIndex,NextIndex),
   go_through([NotYetIndex-V|RestPairs],NextIndex,Rest,More).

% Case of DONE with list traversal
% Only succeed if there are not more pairs left (i.e. no out-of-bound replacements)

go_through([],_CurIndex,L,L).

% ===
% Tests
% ===

:- begin_tests(another_vectorial_replace1).

test(empty)  :- another_vectorial_replace1([],[],LO),
                LO=[].

test(nop_op) :- another_vectorial_replace1([a,b,c,d],[],LO),
                LO=[a,b,c,d].

test(one)    :- another_vectorial_replace1([a],[(1,xxx)],LO),        
                LO=[xxx].

test(two)    :- another_vectorial_replace1([a,b,c,d],[(4,y),(2,x)],LO),
                LO=[a,x,c,y].

test(full)   :- another_vectorial_replace1([a,b,c,d],[(1,e),(2,f),(3,g),(4,h)],LO),
                LO=[e,f,g,h].

test(duplicate_replacement,[fail]) :- another_vectorial_replace1([a],[(1,x),(1,y)],_). 
test(out_of_bounds_high,[fail])     :- another_vectorial_replace1([a],[(2,y)],_).
test(out_of_bounds_low,[fail])    :- another_vectorial_replace1([a],[(0,y)],_).

:- end_tests(another_vectorial_replace1).

rt :- debug(topic),run_tests(another_vectorial_replace1).

增编2

替换使用 maplist/N, foldl/N 和 library(assoc)

递归调用消失在幕后!

https:/github.comdtonhoferprolog_notesblobmastercodevector_replace0.pl。

1
投票

(下面假设对列表中的索引将被排序，按照问题中的例子所示的顺序递增)。

你说的可以写成一个连词

  E=[A,B,C,D], L=[(1,a),(3,c)], solve(E,L), E=[a,B,c,D].

你打算根据适当的定义而持有的。solve/2 你所要找的。但这不就像说

  E=[A|E2],    L=[(1,a)|L2], 
       E2=[B,C,D],      L2=[(3,c)],
                               solve(E2,L2),     E2=[B,c,D], 
                                            E=[a|E2].

? 虽然，有些东西不太合适，这里。c 在 E2 见于 第二 位置，不 3rd，如其条目所示。L2.

但自然而然地, L2 必须从 2的尾巴，因为它是 L 其索引来自 1. 所以，我们必须让 这个 明确。

  E=[A,B,C,D], L=[(1,a),(3,c)], solve(E,L), E=[a,B,c,D]
==
  E=[A,B,C,D], L=[(1,a),(3,c)], solve(E,1,L), E=[a,B,c,D]          % starting index 1
==
  E=[A|E2],    L=[(1,a)|L2], 
       E2=[B,C,D],      L2=[(3,c)],
                               solve(E2,2,L2), E2=[B,c,D], E=[a|E2]

必须，现在 可以，持有。但是，哪里有 a 从 E? 我们在这里的实际意思是

  E=[A|E2],    L=[(1,a)|L2],
               p( (1,a),                1,                    a),   % index match
       E2=[B,C,D],      L2=[(3,c)],
                               solve(E2,2,L2), E2=[B,c,D],          % starting index 2
                                                           E=[a|E2]

与 p/3 定义为

p( (I,A), I, A).

因此，它也必须认为

       E2=[B|E3],       L2=[(3,c)],
                    \+ p(   (3,c),      2,         c),              % index mismatch
             E3=[C,D],     L3=L2,
                               solve(E3,3,L3), E3=[c,D], E2=[B|E3]

L2 是 不 沿着这一步遍历(L3=L2)，因为 p( (3,c), 2, c) 是否 不 持有。

你看到了吗？递归 定义 solve/3 在这里露面？你能把它说完吗？

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.