删除列表的中间元素

Question

我想编写一个 Prolog 程序，将奇数列表中的中间元素删除到另一个列表中。

For example, If we give : delete_mid([1,2,3,4,5],L) then it will produce : L = [1,2,4,5] as answer.

Answer 1

我很惊讶也有点难过，到目前为止，这两个答案都没有采用最明显的方法；你肯定在学校听说过它（我怀疑这可能是 OP 应该做的）。

然而，解释或立即做有点困难，所以首先，这是一个找到中间元素的谓词：

list_mid([H|T], Mid) :-
    list_mid_1(T, T, H, Mid).

list_mid_1([], _, Mid, Mid).
list_mid_1([_,_|Fast], [S|Slow], _, Mid) :-
    list_mid_1(Fast, Slow, S, Mid).

我希望名字是显而易见的。

?- list_mid([], Mid).
false.

?- list_mid([x], Mid).
Mid = x.

?- list_mid([a,x,b], Mid).
Mid = x.

?- list_mid([a,a,x,b,b], Mid).
Mid = x.

?- list_mid([a,a,x,b], Mid).
false.

似乎工作。现在，我可以尝试添加部分，以保留它目前扔掉的东西。

我很忙，所以这花了一段时间。与此同时，Raubsauger 的回答正是我所想的。我没有看到它，而是写了这个：

delete_mid([H|T], L) :-
    delete_mid_1(T, T, H, L).

delete_mid_1([], Rest, _, Rest).
delete_mid_1([_,_|Fast], [H|Slow], Prev, [Prev|Back]) :-
    delete_mid_1(Fast, Slow, H, Back).

它不像 Raubsauger 的解决方案那么简洁，但在其他方面似乎是相同的解决方案。它通过@false 终止测试用例。

我认为list_middle/2谓词就足够了；我再次感到惊讶和悲伤，因为只有 Raubsauger 看到了（或者已经知道了）。

Und täglich grüßt das Murmeltier

Answer 2

现在我也想加入（这个问题的答案是 8）。

delete_mid(Ori, Del):-
    delete_mid(Ori, Ori, Del).

delete_mid([_], [_|Slow], Slow).
delete_mid([_,_|Fast], [H|Slow], [H|Ret]):-    
    delete_mid(Fast, Slow, Ret).

?- delete_mid([1, 2, 3, 4, 5], Del).
Del = [1, 2, 4, 5] ;
false.

?- delete_mid([1, 2, 3, 4], Del).
false.

?- delete_mid(L, []).
L = [_1500] ;
false.

?- dif(A,B), delete_mid([A|_], [B|_]).
false.

关于这个想法：我看到 TA_interns回答关于获取中间元素 ( list_mid) 并想：
这是天才。但是等等......这可以改进。

进一步解释该算法：谓词可用于生成一个列表，该列表类似于没有中间元素的（奇数编号）输入列表。或者，如果此属性成立，它可以测试两个列表。

“天才”部分是不需要计算长度或有计数器，因为它实际上使用输入列表的副本作为计数器。此处和此处解释了原理。

第 1 行和第 2 行创建对同一个列表的两个引用。计数器列表称为快速，元素列表称为慢速。为什么？因为在每个递归步骤中，您从快速列表 ( [_,_|Fast]) 中删除了两个元素，但从元素列表 ( [H|Slow]) 中只删除了一个元素。当快列表中只剩下一个元素时 ( [_]) 你从慢列表中找到中间元素。因此，将其移除并将其余部分放在返回轨道上。在进行递归时H，将从慢速列表中删除的所有元素 ( ) 作为返回列表的头部，递归填充其余部分。

等等，您获得了元素列表的精确副本，只是缺少中间元素。

Answer 3

我认为你需要nth0/4谓词。只需找到中间元素的索引，然后使用nth0/4.

delete_middle(Ls, Ls1) :-
    length(Ls, L),
    divmod(L, 2, Q, 1),   % constrain remainder to be 1: fails on even list
    nth0(Q, Ls, _, Ls1).

生成变体：唯一的问题是 divmod。

divmod1(Dividend, Divisor, Quotient, Remainder) :-
    (   var(Dividend)
    ->  Dividend is Divisor*Quotient+Remainder
    ;   divmod(Dividend, Divisor, Quotient, Remainder)
    ).

delete_middle(Ls, Ls1) :- % Reversed the clauses.
    nth0(Q, Ls, _, Ls1),
    divmod1(L, 2, Q, 1),
    length(Ls, L).

?- dif(A, B), delete_middle([A|_], [B|_]).
false.

?- delete_middle(X, []).
X = [_382] ;
false.