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

user_16650364 0
Viewed 91

I'm new to learn the Prolog, I have a list, which looks like -> [[6, 7, 8,9], [6, 7, 8, 9], [6, 7, 8, 9], [7, 8, 9], [7, 8, 9],[5,6,7]], I want to find the all max length lists in the list, In this case, it should 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.

I could only find the one, I don't know how I find all, please don’t solve this predicate in complicate way or use complicates functor, it’s hard to understand for me.

prolog
4 Answers

The big issue with this problem is the repeated iteration of the list and its sublists, is it not?

I would start with a predicate that iterates over your list-of-lists once, prefixing each sublist with its length, and computing the length of the sublist as it goes:

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)
    .

That's one pass over the list and its sublists.

Now that we have that, all we need is a way to extract sublists of a specified length. That's as easy as this:

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) .

That is another single pass of the outer list. We no longer need to iterate over the sublists themselves.

And then, we just wire up the two predicates:

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

Putting it all together, you get:

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) .

Overall time and space complexity is O(N).

user_4674730

You can do it traversing the list once and keeping the current maximum length found along with the lists that have that maximum length:

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).

Sample run:

?- 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]].
user_4632430

Another possible solution is:

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) ).

Examples:

?- 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]].
user_115359400

Another alternative:

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 ).
user_176283360
Related