logo标签列表

从列表中删除中间元素

listprolog
22

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

例如，如果我们给出： delete_mid([1,2,3,4,5],L)，那么它将产生答案：L = [1,2,4,5]。

3
承诺：将为最佳终止ISO Prolog定义（即，无协同处理）提供赏金，该定义至少在OP的用例中普遍终止，并且还适用于“？- delete_middle（Ls，[]）。 ”和“？- dif（A，B），delete_middle（[A | _]，[B | _]）。” - false
11个回答
10

我很惊讶，有点难过，因为到目前为止，没有一个答案采取最明显的方法；你肯定在学校里听说过这个方法（我猜测这就是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

1
find_mid/2 的第一个参数真的是一个查找吗？ - false
我只是在发布它。 :-) - rajashekar
1
@false 不是的，显然应该是 list_middle/2。 - TA_intern
1
啊，我正在寻找这样的解决方案。（此外，当老布什是总统时，我还在上学，而这个问题不在迪科斯彻的《编程的纪律》中） - David Tonhofer
@TA_intern: 这个问题可能可以通过更好的索引解决。它对应于append(Xs,Ys,[])。但是delete_mid(L，[a，b])不能仅通过索引解决。 - false
显示剩余3条评论
8

现在我也想加入（回答这个问题的第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 answer 关于获取中间元素（list_mid）的方法，我想：
这太聪明了。但是等等……这可以改进。

进一步解释一下算法：谓词可以用来生成一个类似于输入列表（奇数编号）但没有中间元素的列表。或者它可以测试两个列表是否具有此属性。
“天才”的部分在于不需要计算长度或拥有计数器，因为它实际上使用输入列表的副本作为计数器。该原则在这里和这里中得到了解释。
第1行和第2行创建了对同一列表的两个引用。计数器列表称为快速列表，元素列表称为慢速列表。为什么？因为在每个递归步骤中，您从快速列表([_,_|Fast])中剥离两个元素，但只从元素列表([H|Slow])中剥离一个元素。当快速列表中只剩下一个元素([_])时，您就会命中慢速列表的中间元素。因此，将其删除并将其余部分放在返回轨道上。在递归向前进行时，将从慢速列表中删除的所有元素(H)作为返回列表的头部，并由递归填充其余部分。
你现在得到了一个元素列表的精确副本，只是中间的元素缺失。
2
到目前为止最佳解决方案。 - TA_intern
1
我不想太快地提供一个可行的解决方案，因为我认为这并不是必要的。你是唯一一个注意到它的人。这个想法的功劳归于没有特定的人。你的最终解决方案可能比我想出来的更好。 - TA_intern
正确的，除了不是一个副本，而是原始列表本身，其中有两个指针，一个速度是另一个的两倍。通过这种递归没有回头路，因为它是尾递归。规则头中的[H|Ret]预先处理，在递归调用之前完成，填充空白Ret。请参见1。 - Will Ness
哦不，整个编辑，为什么？这只是一个小问题... - Will Ness
1
我冒昧地恢复了它，并进行了一些小的修改... :) - Will Ness
5

我认为你需要使用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.
1
@Raubsauger：这个问题限定在“奇数列表”中。在偶数长度的列表中，您将什么定义为中间元素？可以忽略删除或者也可以删除其中两个。 - rajashekar
2
@DavidTonhofer 如果长度尚未被限制为奇数，则将divmod中的余数设置为1即可解决问题。 - rajashekar
1
@false: 重新排列子句。将nth0谓词放在最前面，然后它就会终止。 - rajashekar
1
@false 这就是 Prolog 的问题所在 - 你永远不知道谓词会遇到什么情况，但你也不愿意添加一堆 must_be 来限制使用实际已知可行的情况。 - David Tonhofer
1
使用 listing(divmod1) 查看如何正确缩进此内容。 - false
显示剩余12条评论
4

使用 nth0/4 方法的解决方案效率很高，但我们可以采用声明式的方式来解决吗？

middle_less(InList,MiddlelessList,Middle) :-
   append([Prefix,[Middle],Suffix],InList),
   length(Prefix,Len),
   length(Suffix,Len),
   append(Prefix,Suffix,MiddlelessList).

这基本上是Prolog形式的问题陈述。

它也可以工作：

:- begin_tests(middleless).

test("empty list",fail) :- middle_less([],_,_).

test("1-element list",[true([MLL,M] == [[],a]),nondet]) :-
   middle_less([a],MLL,M).

test("2-element list",fail) :- 
   middle_less([a,b],_,_).

test("3-element list",[true([MLL,M] == [[a,c],b]),nondet]) :-
   middle_less([a,b,c],MLL,M).

:- end_tests(middleless).

所以：

?- run_tests.
% PL-Unit: middleless .... done
% All 4 tests passed
true.

但是对于一个包含1001个元素的列表：

?- length(L,1001),time(middle_less(L,MLL,M)).
% 757,517 inferences, 0.110 CPU in 0.111 seconds (99% CPU, 6862844 Lips)

有一天，编译器会自动地将middle_less的规范转变为高效的解决方案。

1
将两个 length/2 移动到同一个__length/2 作为第一个目标可以提高计时 5 倍，但是 @false 提出的终止问题无法用这种方式解决。放弃... - CapelliC
1
如何看待以下代码：middle_less(InList,MiddlelessList,Middle) :- list_onelesslong(InList, MiddlelessList), <同上>, 其中 list_onelesslong([_], [])。 list_onelesslong([_X | Xs], [_Y | Ys]) :- list_onelesslong(Xs, Ys).。这使得谓词能够生成答案。 - Isabelle Newbie
3
delete_middle([], [], _MiddleDeletedPrefix) -->
    [_Middle].
delete_middle([L | Left], [R | ReversedRight], [L | MiddleDeletedPrefix]) -->
    [L],
    delete_middle(Left, ReversedRight, MiddleDeletedPrefix),
    [R].

delete_middle(List, MiddleDeleted) :-
    phrase(delete_middle(Left, ReversedRight, MiddleDeleted), List),
    reverse(ReversedRight, Right),
    append(Left, Right, MiddleDeleted).

 

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

?- delete_middle(Ls, []).
Ls = [_2542] ;
false.

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

?- delete_middle(List, MiddleDeleted).
List = [_2368],
MiddleDeleted = [] ;
List = [_2368, _2392, _2374],
MiddleDeleted = [_2368, _2374] ;
List = [_2368, _2392, _2416, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2398, _2374] ;
List = [_2368, _2392, _2416, _2440, _2422, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2416, _2422, _2398, _2374] ;
List = [_2368, _2392, _2416, _2440, _2464, _2446, _2422, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2416, _2440, _2446, _2422, _2398, _2374] .  % etc.
你可以将“Left”列表保持打开状态，并将其尾部与“Right”统一，而无需使用“append/3”。 - Isabelle Newbie
1
针对您的最后一个示例，请尝试：?- delete_middle(X, Y), numbervars(X-Y). 这样稍微容易一些。 - TA_intern
我一直在想什么时候会看到一个不同的列表答案。 :) - Guy Coder
2
新版本，现在更具确定性：
delete_mid(List, MiddleDeleted) :-
    List = [_ | Tail],
    gallop(Tail, MiddleDeleted, List, MiddleDeleted).

gallop([], [], [_Middle | Xs], Xs).
gallop([_,_ | Fast1], [_,_ | Fast2], [X | Xs], [X | Ys]) :-
    gallop(Fast1, Fast2, Xs, Ys).

与以往的答案相比，最新的答案是它以双倍速度遍历两个列表，并同时复制前缀。为了保证确定性，它需要至少对前两个参数进行浅索引，但SWI-Prolog已经实现了这一点：

?- delete_mid([1, 2, 3, 4, 5], MiddleDeleted).
MiddleDeleted = [1, 2, 4, 5].

?- delete_mid(Xs, []).
Xs = [_2008].

?- delete_mid(Xs, [a, b]).
Xs = [a, _2034, b].

?- dif(A, B), delete_mid([A | _], [B | _]).
false.
1
@false 现在可能已经足够确定性了... :-) - Isabelle Newbie
1
显然，这是进步。 - false
1

在TA_intern提出的查找中间值算法的基础上进行改进：

%! list_without_middle(SOURCEs,TARGETs)

list_without_middle(SOURCEs,TARGETs)
:-
list_middle(SOURCEs,_MIDDLE_,PREFIXs,SUFFIXs) ,
lists:append(PREFIXs,SUFFIXs,TARGETs)
.

%!  list_middle(LISTs,MIDDLE,PREFIXs,SUFFIXs)

list_middle([ITEM|LISTs],MIDDLE,PREFIXs,SUFFIXs)
:-
list_middle(LISTs,LISTs,ITEM,MIDDLE,PREFIXs,SUFFIXs)
.

%!  list_middle(FASTs,SLOWs,ITEM,MIDDLE,PREFIXs,SUFFIXs)

list_middle([],SLOWs,ITEM,ITEM,[],SLOWs) .

list_middle([_,_|FASTs],[ITEM|SLOWs],PREVIOUS_ITEM,MIDDLE,[PREVIOUS_ITEM|PREFIXs],SUFFIXs)
:-
list_middle(FASTs,SLOWs,ITEM,MIDDLE,PREFIXs,SUFFIXs)
.


?- list_without_middle([a,b,c],Ys).
Ys = [a, c].

?- list_without_middle([a,c],Ys).
false.

?- list_without_middle([a,b,c,d,e],Ys).
Ys = [a, b, d, e].

?- 


?- list_without_middle(Xs,Ys) .
Xs = [_924],
Ys = [] ;
Xs = [_924, _930, _936],
Ys = [_924, _936] ;
Xs = [_924, _930, _936, _948, _954],
Ys = [_924, _930, _948, _954] %.e.t.c.


?- list_middle([a,b,c],MIDDLE,PREFIXs,SUFFIXs).
MIDDLE = b,
PREFIXs = [a],
SUFFIXs = [c].

?- list_middle([a,c],MIDDLE,PREFIXs,SUFFIXs).
false.

?- list_middle([a,b,c,d,e],MIDDLE,PREFIXs,SUFFIXs).
MIDDLE = c,
PREFIXs = [a, b],
SUFFIXs = [d, e].

?- 


?- list_without_middle(Ls,[]) .
Ls = [_4364] ;
ERROR: Out of global stack
?- list_without_middle([a],Ys).
Ys = [].

?- dif(A,B) , list_without_middle([A|_],[B|_]) .
ERROR: Out of global stack
?-
1
这个解决方案保持一个计数器，以在“取出”中间项后将尾部统一为正确长度的列表：
without_middle(Ls, Ls1):-
  without_middle(Ls, 0, Ls1).
  
without_middle([_Mid|Tail], Len, Tail):-
  length(Tail, Len).
without_middle([Item|Tail], Len, [Item|NTail]):-
  succ(Len, Len1),
  without_middle(Tail, Len1, NTail).
这种微小的变化更直接地嵌入了第二半部分的计数+长度+统一，从而为大型列表提供了更好的性能结果。
without_middle(Ls, Ls1):-
  without_middle(Ls, [], Ls1).

without_middle([_Mid|Tail], Tail, Tail).
without_middle([Item|Tail], RTail, [Item|NTail]):-
   without_middle(Tail, [_|RTail], NTail).

示例测试用例：

?- without_middle([a,b,c,d,e,f,g], L).
L = [a, b, c, e, f, g] ;
false.

?- without_middle([a,b,c,d,e,f], L).
false.

?- without_middle(L, []).
L = [_552] ;
false.

?- dif(A,B), without_middle([A|_], [B|_]).
false.
我知道这只是一个玩具问题...无论如何，尝试在稍长的列表上计时你的解决方案（超过10000个元素）；然后将其与Raubsauger的解决方案进行比较。 - TA_intern
真的！Raubsager算法比这个好多了。 - gusbro
@TA_intern 添加了一个小变化，可以得到可比较的时间。 - gusbro
1
利用append/3：
del_mid([_], []).         % if input only has one element => output is []
del_mid([H|T], [H|X]) :- 
  append(M, [Litem], T),  % M = list without first and last (Litem) element
  del_mid(M, R),          % Apply on M; if M is only one item => R will be []
  append(R, [Litem], X).  % X = R + [last item] => which gets added as result's tail

一些例子：

?- del_mid([], X).
false.

?- del_mid([a], X).
X = [] ;
false.

?- del_mid([a,b], X).
false.

?- del_mid([a,b,c], X).
X = [a, c] ;
false.

?- del_mid([a,b,c,d,e,f,g], X).
X = [a, b, c, e, f, g] ;
false.
0

这不是一个直截了当或更优的答案。

delete_middle1(Ls, Ls1) :- delete_middle1_(Ls, Ls, [], Ls1).
delete_middle1_([X | Cs], [_, _ | Ds], Acc, L) :-
    delete_middle1_(Cs, Ds, [X | Acc], L).
delete_middle1_([_ | Cs], [_], Acc, L) :-  revappend(Acc, Cs, L).

revappend([], L, L).
revappend([X | L1], L2, L3) :- revappend(L1, [X | L2], L3).

这种方法在处理链表和指针时非常有效。当一个指针到达末尾时，另一个指针会接近中间。然后我们就可以删除元素了。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接