prolog - 在 Prolog 中找到最长的列表？

Question

我需要编写一个谓词longestList/2，如果L2是最长的，则满足longestList(L1,L2)来自列表 L1 的嵌套列表。

?- longestList([[1],[1,2],[1,2,3],[1,2,3,4]],LI).
LI = [[1, 2, 3, 4]] ;
No
?- longestList([[a,b,c],[d,e],[f,g,h]],LI).
LI = [[f, g, h],[a,b,c]];
No

有人可以帮助我凭直觉来解决这个问题吗？

Answer 1

这是基本递归方法的概述。不像 @CapelliC 给出的答案那么清晰，但同样简单。

这个想法是遍历列表并跟踪迄今为止您见过的最长列表，以及它的长度是多少。然后，您递归地单步遍历列表，并在条件表明如此时更新递归的这些参数。这是对用于执行递归“最大列表元素”谓词的技术的轻微阐述。为此，您需要设置一个包含更多参数的调用(当前最长的列表及其长度)。

longestList([], []).
longestList([L|Ls], LongestList) :-
    length(L, Length),
    % Start with the first element (L) being my best choice so far
    longestList(Ls, L, Length, LongestList).

这是带有新参数的扩展谓词。

longestList([L|Ls], LongestListSoFar, GreatestLengthSoFar, LongestList) :-
    % Here, you need to examine L and determine if it should supersede
    %  the longest list so far and its length. You need to keep in mind that
    %  if the length of L is the same as the max length so far, then I
    %  may choose to keep the LongestListSoFar, or choose L. Both are
    %  valid solutions for this call. This is a good place to use the `;`
    %  operator, and to be cautious about parenthesizing expressions since
    %  the comma has higher precedence than the semi-colon.
    %  Also, you'll need to make a recursive call to longestList(Ls, ??, ??, LongestList).
    %  The arguments to the recursion will depend upon which way the decision flow goes.
    %
    % After all that to-do, don't let it scare you: it's about 5 lines of code :)
    %
longestList([], LongestListSoFar, ??, ??).
    % Fill in the ??. What should they be at list's end ([])?
    %   Do I even care now what the 3rd argument is?

希望这足以给您一些思考以取得进步。或者，使用 @CapelliC 的解决方案并编写 member_length/3 谓词。 :) 请注意，正如在他的解决方案中一样，如果有多个列表，上述解决方案将在回溯时生成每个最大列表。因此，如果您想在一个列表中获取所有解决方案，可以使用 findall/3。