按索引号在列表之间移动元素？

Question

我正在尝试在 LoL（列表的列表）结构中的列表之间移动元素。我可以弄清楚如何 select 列表并移动元素，但我不知道如何重建生成的 LoL。这是部分功能：

 move(From, To, State=[P1,P2,P3], NewState=[NP1, NP2, NP3]) :- 
    nth1(From, State, FL), nth1(To, State, TL), move_elem(FL, TL, NewFL, NewTL),
   .....whats here?...
   .. NewState should be build out of NewTL,NewFL and one of P1,P2,P3...
   .. the order of the lists should be preserved..

move_elem/4 已实施。 From & To 是整数并指定将参与移动操作的列表位置。

目前 LoL 是 3 个列表的列表，但我希望将来能参数化列表的数量。

State is LoL before the move, NewState is the LoL after the move.

?- move_elem([1,2,3], [4,5,6], F,T).
F = [2, 3],
T = [1, 4, 5, 6].

nth1/3 似乎工作正常。

?- L=[[1,2],[3,4],[5,6]], nth1(2,L,El).
L = [[1, 2], [3, 4], [5, 6]],
El = [3, 4].

move() shold 将元素从三个列表之一移动到另一个。 From 和 To 是列表的索引 f.e.

LoL = [[1,2],[3,4],[5,6]]
move(1,3, LoL, NewLoL)
NewLoL = [[2],[3,4],[1,5,6]]

move(2,1, LoL, NewLoL)
NewLoL = [[3,1,2],[4],[1,5,6]]

将顶部元素从 list-1 移到 list-3。

Answer 1

您可以这样实现move/4：

appendHead(T,H,[H|T]).
removeHead([_|T],T).

insert(_,_,_,_,_,[],[]).
insert(C,I2,L1,L2,C,[_|TI],[L1|TO]):-
    C1 is C+1,
    insert(C,I2,L1,L2,C1,TI,TO).
insert(I1,C,L1,L2,C,[_|TI],[L2|TO]):-
    C1 is C+1,
    insert(I1,C,L1,L2,C1,TI,TO).
insert(I1,I2,L1,L2,C,[HI|TI],[HI|TO]):-
    I1 \= C,
    I2 \= C,
    C1 is C+1,
    insert(I1,I2,L1,L2,C1,TI,TO).

move(I1,I2,LIn,LOut):-
    nth1(I1,LIn,L1),
    nth1(I2,LIn,L2),
    nth1(1,L1,E1),
    removeHead(L1,L1R),
    appendHead(L2,E1,L2F),
    insert(I1,I2,L1R,L2F,1,LIn,LOut).

?- LoL = [[1,2],[3,4],[5,6]], move(1,3, LoL, NewLoL).
LoL = [[1, 2], [3, 4], [5, 6]],
NewLoL = [[2], [3, 4], [1, 5, 6]].
false.

?- LoL = [[2], [3, 4], [1, 5, 6]], move(2,1, LoL, NewLoL).
LoL = [[2], [3, 4], [1, 5, 6]],
NewLoL = [[3, 2], [4], [1, 5, 6]].
false.

?- LoL = [[1,2],[3,4],[5,6]], move(2,1, LoL, NewLoL).
NewLoL = [[3,1,2],[4],[1,5,6]].
false.

如果要防止回溯，只需在insert/4的每个定义后添加一个cut !即可（不会得到false）。

Answer 2

Prolog 进行 depth-first 搜索，这意味着它将尝试通过探索所有可能的解决方案路径来达到目标。每次有多个可用路径时，它都会创建一个选择点，然后从上到下依次选择。这意味着，如果一个选择立即失败，将调用下一个。这使您可以非常清楚地创建路径，并且可以为其做出选择。在 Prolog 中，包括列表在内的所有原子实际上都是不可变的。你想要做的是从第一个列表构建第二个列表，可能以不同的顺序或更少的元素、更多的元素、替换的元素等。

我在这里使用矩阵中的单元格（点（X，Y），值）坐标替换行中的单元格作为示例。重建列表的三种选择。

已到达列表末尾，这是结束条件并结束新列表。
检查了列表的第一个单元格，坐标与替换的不匹配，因此按原样放置在新列表中。
列表的第一个单元格与坐标匹配，因此将该元素放入新列表并通过添加剩余未选中的元素作为尾部来关闭它。

这导致代码：

%coordinate not found, return the list as is
replace_cell(_,_,[],[]).
%no match, X already extracted from Element to reduce calls 
replace_cell(X, Element, [RowElement|Tail], [RowElement|NewTail]) :-
    RowElement \= cell(point(X,_),_),
    replace_cell(X, Element, Tail, NewTail).
%match
replace_cell(X, Element, [cell(point(X,_),_)|Tail], [Element|Tail]).

这是您可能习惯的标准递归。设定了目标，得到了答案，Prolog 开始回退调用，填充我们在回退时打开的变量。然后那些填充的变量成为下一个返回调用的输出。

然后要用多层列表来做，我们只需要弄清楚我们需要将哪个列表传递给下一个更具体的调用。在此矩阵示例中，它是一个正方形，因此所有列共享一个 X，所有行共享一个 Y 坐标。为了弄清楚我们需要哪一行，我们可以将整个矩阵输入一个简单的谓词来检查 Y。请注意，我们实际上还没有修改矩阵，只是标识了行。这主要是为了保持代码的可读性。

%are there any rows left?
move_to_row(_, [], []).
%is element's Y equal to row Y?
move_to_row(Y, [Row|_], Row) :- Row = [cell(point(_,Y),_)|_].
%move to next row
move_to_row(Y,[_|Tail], Row) :- move_to_row(Y,Tail,Row).

替换行中的元素后，由于我们同时拥有旧行和新行，我们可以识别旧行并用新行重建矩阵。

replaceElement(_,_,[],[]).
replaceElement(Replacable, Replacement, [Item|List], [Replacable|NewList] ) :-
   Item \= Replacable,
   replaceElement(Replacable, Replacement, List, NewList),
replaceElement(Replacable, Replacement, [Replacable|List], [Replacement|List] ) :- 
   !.

如此有效，列表中的位置由我们向下遍历列表的顺序保持，然后在向上重建新列表。

对于列表 [1,2,3]，[Head|Tail] 给我们 Head = 1, Tail = [2,3]。如果我们再次调用 [Head|Tail]，它会返回 Head = 2, Tail = [3]。在返回的路上，恰恰相反，Head 被附加到 Tail 的前面。通过将列表的每一层可视化为它自己的可识别类型并为它们提供自己的标识符，无论您要嵌套列表中有多少列表，都应该非常简单地有效地遍历它们。矩阵是一个 2d 矩形，但是例如通过将 cell 内的坐标作为列表并添加 Z 轴，它可以很容易地变成立方体或具有超过 3 个维度的更复杂的东西。

Answer 3

使用length/2 and append/3:

move(From, To, State, NewState):-
  length([_|HState], From),
  length([_|HNewState], To),
  append(HState, [[Item|L]|TState], State),
  append(HState, [L|TState], MState),
  append(HNewState, [NL|TNewState], MState),
  append(HNewState, [[Item|NL]|TNewState], NewState).

我们的想法是使用 length/2 生成一个长度为 From-1 的未实例化变量列表和另一个长度为 To-1 的列表（因此我们从长度为 From 和 To 的列表中跳过一个元素）。

然后append/3可用于将State分成两部分或连接两个列表。

第一次调用 append 会将 State 拆分为包含 From-1 元素的列表 HState 和包含其余元素的第二个列表。其余部分的第一个元素进一步分为两部分（要移动的项目和该元素的其余部分）。

第二次调用 append 连接两个部分，不包括要移动的项目。

第三次和第四次追加调用重复了这个想法，虽然这次它们用于将移动的项目添加到目标位置。

按索引号在列表之间移动元素？

Move elements between lists by index number?

element

list

move

prolog