时间戳

首页 > 解决方案 > Prolog - 将列表分成两半，反转前半部分

list - Prolog - 将列表分成两半，反转前半部分

问题描述

我被要求将一个字母列表放入两个大小相等的列表（我猜是原始列表大小相同）或一个比另一个大一个元素（奇数大小的列表），并在我的时候反转第一个米在它。

查询输出示例：

?- dividelist2([a,b,c,d,e,f], L1,L2).
L1 = [c,b,a]
L2 = [d,e,f]

?- dividelist2([a,b,c,d,e], L1,L2).
L1 = [c,b,a]
L2 = [d,e]
% OR
L1 = [b,a]
L2 = [c,d,e]

我已经达到了这个解决方案，但我觉得它有问题。如果我遗漏了什么，请告诉我...如何获得最后的输出？（输出的两个选项，我的意思是）

dividelist2(L, X, B) :-
  (  append(A, B, L),
     length(A, O),
     length(B, N),
     (  (O-1) =:= N
     ;  (O+1) =:= N
     ;  O     =:= N
     ),
     !
  ), reverse(A, X).

reverse(List, Rev) :-
        reverse(List, Rev, []).

reverse([], L, L).
reverse([H|T], L, SoFar) :-
        reverse(T, L, [H|SoFar]).

提前致谢！

标签： listsplitprologreverse

解决方案

谢谢@WillNess，我在这里使用龟/兔技巧有一个完整的解决方案。这个技巧背后的想法是你同时遍历列表，乌龟一个元素一个元素地遍历，兔子一次两个元素遍历。当野兔列表为空时，您知道您位于列表的中间。这内联了一个常见的累加器模式，用于一次性反转列表，这就是我们产生结果的前半部分的方式。结果的后半部分就是列表的剩余部分——也就是说，乌龟列表。

divide(List, Left, Right) :-
    reverse(List, List, [], Left, Right).

% reverse(Tortoise, Hare, ReverseAccumulator, RevFirstHalf, SecondHalf)
reverse(Right, [], Left, Left, Right).
reverse([X|Xs], [_,_|Rem], Acc, Left, Right) :-
    reverse(Xs, Rem, [X|Acc], Left, Right).

正如你所看到的，兔子只是在这里被一次遍历两次，直到它变空，这触发了我们的基本情况。这适用于偶数长度列表。

对于奇数长度的列表，我们必须通过注意野兔是单项列表来处理它们。然后我们需要再产生两个解决方案，所以我们有两个用于单项列表情况的子句：一个将下一个乌龟项放入前半个列表，一个将其放入后半个列表：

reverse([X|Xs], [_], Acc, Left, Right) :-
    reverse([X|Xs], [], Acc, Left, Right).
reverse([X|Xs], [_], Acc, Left, Right) :-
    reverse(Xs, [], [X|Acc], Left, Right).

这会产生您想要的结果。一开始有点难以理解发生了什么，但它比公认的答案更有效，可能是因为它没有分配那么多。作为比较，我在一个包含 500 万个条目的列表上运行了两者；这个版本跑得更快一些：

?- length(L, 5000000), time(splitflip(L, Left, Right)).
% 5,000,014 inferences, 0.806 CPU in 0.806 seconds (100% CPU, 6200835 Lips)
L = [_58, _64, _70, _76, _82, _88, _94, _100, _106|...],
Left = [_15000052, _15000046, _15000040, _15000034, _15000028, _15000022, _15000016, _15000010, _15000004|...],
Right = [_15000058, _15000064, _15000070, _15000076, _15000082, _15000088, _15000094, _15000100, _15000106|...].

?- length(L, 5000000), time(divide(L, Left, Right)).
% 2,500,001 inferences, 0.567 CPU in 0.568 seconds (100% CPU, 4405613 Lips)
L = [_850, _856, _862, _868, _874, _880, _886, _892, _898|...],
Left = [_15000844, _15000838, _15000832, _15000826, _15000820, _15000814, _15000808, _15000802, _15000796|...],
Right = [_15000850, _15000856, _15000862, _15000868, _15000874, _15000880, _15000886, _15000892, _15000898|...] .

编辑：原始答案如下。

这只是部分解决方案。我错过了一些关于如何将其转换为完整解决方案的明显内容，而且我目前没有太多时间来完成它，但我认为无论如何分享它可能很有用。并且可能另一个回答者会立即看到问题出在哪里。

我在这里的计划基本上是反转列表并跟踪我从一开始就进入递归调用的索引，并从结束跟踪我在递归调用中的索引。有了这个，如果索引匹配，我们采用反转的前缀和后缀，这就是结果。我们可以使用单独的谓词将“匹配”定义为索引彼此在 1 以内。

reverse(_, [], 0, Z, Z).
reverse(I, [X|Xs], J1, Z, Acc) :-
    succ(I, I1),
    reverse(I1, Xs, J, Z, [X|Acc]),
    succ(J, J1).

当在trace.输出中查看时，我认为我们需要的部分组合在此代码中可见：

[trace]  ?- reverse(0, [a,b,c,d], _, R, []).
   Call: (8) reverse(0, [a, b, c, d], _694, _696, []) ? creep
   Call: (9) succ(0, _964) ? creep
   Exit: (9) succ(0, 1) ? creep
   Call: (9) reverse(1, [b, c, d], _972, _696, [a]) ? creep
   Call: (10) succ(1, _970) ? creep
   Exit: (10) succ(1, 2) ? creep
   Call: (10) reverse(2, [c, d], _978, _696, [b, a]) ? creep
   Call: (11) succ(2, _976) ? creep
   Exit: (11) succ(2, 3) ? creep
   Call: (11) reverse(3, [d], _984, _696, [c, b, a]) ? creep
   Call: (12) succ(3, _982) ? creep
   Exit: (12) succ(3, 4) ? creep
   Call: (12) reverse(4, [], _990, _696, [d, c, b, a]) ? creep
   Exit: (12) reverse(4, [], 0, [d, c, b, a], [d, c, b, a]) ? creep
   Call: (12) succ(0, _988) ? creep
   Exit: (12) succ(0, 1) ? creep
   Exit: (11) reverse(3, [d], 1, [d, c, b, a], [c, b, a]) ? creep
   Call: (11) succ(1, _988) ? creep
   Exit: (11) succ(1, 2) ? creep
   Exit: (10) reverse(2, [c, d], 2, [d, c, b, a], [b, a]) ? creep
   Call: (10) succ(2, _988) ? creep
   Exit: (10) succ(2, 3) ? creep
   Exit: (9) reverse(1, [b, c, d], 3, [d, c, b, a], [a]) ? creep
   Call: (9) succ(3, _694) ? creep
   Exit: (9) succ(3, 4) ? creep
   Exit: (8) reverse(0, [a, b, c, d], 4, [d, c, b, a], []) ? creep
R = [d, c, b, a] .

特别注意这一行：

   Exit: (10) reverse(2, [c, d], 2, [d, c, b, a], [b, a]) ? creep

如您所见，此时我们有 I = J = 2，并且我们有一个 list[b,a]和一个 list [c,d]。这让我希望这很接近，但无论出于何种原因，我都没有看到通向完整解决方案的桥梁。也许你会的！

推荐阅读