在序言中查找列表的最大长度的简单方法是什么？

Question

我刚开始学习 Prolog，我有一个列表，看起来像 -> [[6, 7, 8,9], [6, 7, 8, 9], [6, 7, 8, 9], [7, 8, 9], [7, 8, 9], [5,6,7]], 我想找到列表中的所有最大长度列表，在这种情况下，它应该 return [[6,7,8,9],[6,7,8,9],[6,7,8,9]]

my code


maxlist([A],A).
maxlist([A,B|Rest],Max):-
    maxlist([B|Rest],Maxrest),
    max(A,Maxrest,Max).

max(A,B,A):-
    length(A,N1),
    length(B,N2),
    N1>N2.
max(A,B,B):-
    length(A,N1),
    length(B,N2),
    N2>N1.

我只能找到一个，我不知道我是怎么找到所有的，请不要复杂地解决这个谓词或使用复杂的函子，我很难理解。

Answer 1

这个问题的大问题是列表及其子列表的重复迭代，不是吗？

我将从一个遍历您的 list-of-lists 一次的谓词开始，为每个子列表添加其长度前缀，并计算子列表的长度：

map_lengths( Xs, L, X1 ) :- map_lengths(Xs,0,L,X1) .
    
map_lengths( []     , M , M , []       ) .
map_lengths( [X|Xs] , T , M , [L:X|Ys] ) :-
    length(X,L),
    T1 is max(L,T),
    map_lengths(Xs,T1,M,Ys)
    .

这是列表及其子列表的一次传递。

既然我们已经有了，我们所需要的只是一种提取指定长度子列表的方法。就这么简单:

lists_of_length( _ , [] , [] ) .
lists_of_length( L , [L:X|Xs] , [X|Ys] ) :- !, lists_of_length(L,Xs,Ys) .
lists_of_length( L , [_:_|Xs] ,    Ys  ) :-    lists_of_length(L,Xs,Ys) .

这是外部列表的另一遍。我们不再需要遍历子列表本身。

然后，我们连接两个谓词：

longest( Xs , Ys ) :-
    map_lengths( Xs, L, X1 ) ,
    lists_of_length(L,X1,Ys)
    .

把它们放在一起，你得到：

https://swish.swi-prolog.org/p/VyUrjJjD.pl


longest( Xs , Ys ) :-
    map_lengths( Xs, L, X1 ) ,
    lists_of_length(L,X1,Ys)
    .

map_lengths( Xs, L, X1 ) :- map_lengths(Xs,0,L,X1) .
    
map_lengths( []     , M , M , []       ) .
map_lengths( [X|Xs] , T , M , [L:X|Ys] ) :-
    length(X,L),
    T1 is max(L,T),
    map_lengths(Xs,T1,M,Ys)
    .

lists_of_length( _ , [] , [] ) .
lists_of_length( L , [L:X|Xs] , [X|Ys] ) :- !, lists_of_length(L,Xs,Ys) .
lists_of_length( L , [_:_|Xs] ,    Ys  ) :-    lists_of_length(L,Xs,Ys) .

总时间和 space 复杂度为 O(N)。

Answer 2

您可以遍历列表一次并保留找到的当前最大长度以及具有该最大长度的列表：

maxlist(L, ML):-
  maxlist(L, 0-[], ML).
  
maxlist([], _-ML, ML).
maxlist([A|L], MaxLen-ML, ML2):-
  length(A, Len),
  compare(C, Len, MaxLen),
  memberchk(C-MaxLen1/ML1, [(<)-MaxLen/ML, (=)-MaxLen/[A|ML], _-Len/[A]]),
  maxlist(L, MaxLen1-ML1, ML2).

样本运行：

?- maxlist([[6, 7, 8,9], [6, 7, 8, 9], [6, 7, 8, 9], [7, 8, 9], [7, 8, 9],[5,6,7], [1,2,3,4,5]], ML).
ML = [[1, 2, 3, 4, 5]].

Answer 3

另一种可能的解决方案是：

maxlist(ListOfLists, Answer) :-
    maxlist(ListOfLists, -inf, [], Answer).

maxlist([], _, Answer, Answer).

maxlist([List|Lists], Max, Acc, Answer) :-
    length(List, N),
    (   N = Max ->  maxlist(Lists, Max, [List|Acc], Answer)
    ;   N > Max ->  maxlist(Lists,  N,  [List],     Answer)
    ;               maxlist(Lists, Max, Acc,        Answer) ).

示例：

?- maxlist([[6,7,8,9], [6,7,8,9], [6,7,8,9], [7,8,9], [7,8,9], [5,6,7]], M).
M = [[6, 7, 8, 9], [6, 7, 8, 9], [6, 7, 8, 9]].

?- maxlist([[1,2,3],[4,5,6,7,8,9],[0]], M).
M = [[4, 5, 6, 7, 8, 9]].

?- maxlist([[1,2,3], [4,5,6,7], [8], [9,0,1], [2,3,4,5]], M).
M = [[2, 3, 4, 5], [4, 5, 6, 7]].

Answer 4

另一种选择：

max_len_lists(LstLists, LstMaxLenFilter) :-
    max_len_lists_(LstLists, _LenMax, LstMaxLenFilter),
    % No need to check for alternatives
    !.

max_len_lists_([], 0, []).
max_len_lists_([H|T], Len, LstMax) :-
    length(H, LenH),
    % Use recursion to check the rest of the list
    max_len_lists_(T, LenT, F),
    ( LenH = LenT -> Len = LenH, LstMax = [H|F]
    ; LenH > LenT -> Len = LenH, LstMax = [H]
    ; Len = LenT, LstMax = F ).

在序言中查找列表的最大长度的简单方法是什么？

What is the simple way to find the max length of a list in prolog?

prolog