How do I find the longest list in a list of lists?

问题:

I have a list of lists, and I need to find the longest one of them. If there are more than one with the same length it's the same which it returns. Thanks.

回答1:

Here is a general predicate that scans a list to find a single member defined by a given goal.

select_element(Goal, [Head | Tail], Selected) :-
    select_element(Goal, Tail, Head, Selected).


select_element(_Goal, [], Selected, Selected).

select_element(Goal, [Head | Tail], Current, FinalSelected) :-
    call(Goal, Head, Current, Selected),
    select_element(Goal, Tail, Selected, FinalSelected).

Lets say you define a predicate

get_bigger_number(N1, N2, N) :-
    N is max(N1, N2).

Now you can execute:

?- select_element(get_bigger_number, [5, 1, -2, 10, 3.2, 0], Selected).

Selected = 10

So all you need to do now is define a predicate get_longer_list(L1, L2, L), and use it instead of get_bigger_number/3.

Of course, using a general predicate like select_element/3 might not be very efficient. For example, you should try to avoid calculating the length of the same list several times, because this calculation is slow in Prolog (at least if implemented in Prolog in the standard way).

回答2:

Please consider my aproach.

longest([L], L) :-
   !.
longest([H|T], H) :- 
   length(H, N),
   longest(T, X),
   length(X, M),
   N > M,
   !.
longest([H|T], X) :-
   longest(T, X),
   !.

Then you can consult it:

?- longest([[1]], N).
N = [1] ;

?- longest([[1],[2]], N).
N = [2] .

?- longest([[1],[2], [3,3,3], [2]], N).
N = [3, 3, 3] ;

?- longest([[1],[2], [3,3,3], [2]], N).
N = [3, 3, 3].

?- longest([[1],[2], [3,3,3], [2], [4,4,4,4]], N).
N = [4, 4, 4, 4] .

?- longest([[1],[2], [3,3,3], [2], [4,4,4,4]], N).
N = [4, 4, 4, 4] ;

Greets!

回答3:

We define longest/2 based on meta-predicate max_of_by/3 used in tandem with length/2:

longest(Xss,Ys) :-
   max_of_by(Ys,Xss,length).

Sample queries:

?- longest([[1],[2]],Xs).      % we expect   multiple solutions
  Xs = [1]                
; Xs = [2].                    % we    _get_ multiple solutions

?- longest([[2,1,3],[7,5],[1,8,2,3,1],[2,7,1,4]],Xs).
Xs = [1,8,2,3,1].              % succeeds deterministically

回答4:

Here is another approach that is efficient and easy to understand. The idea is to find the lengths of all lists in the list, use max_list to get the length of the longest list, and then find a list that is that long. This has the benefit that it will return all lists of the longest length.

lengths([],[]).
lengths([H|T], [LH|LengthsT]) :-
    length(H, LH),
    lengths(T, LengthsT).

lengthLongest(ListOfLists, Max) :-
    lengths(ListOfLists, Lengths),
    max_list(Lengths, Max).

longestList(ListOfLists, Longest) :-
    lengthLongest(ListOfLists, Len),
    member(Longest, ListOfLists),
    length(Longest, Len).

回答5:

% Correct again.

longest(LL,LX) :-
        findmax(Len,(append(_,[L|_],LL),length(L,Len)),MaxLen),
        append(_,[LX|_],LL),
        length(LX,MaxLen).

findmax(V,P,Max) :-
        findall(V,P,L),
        max(L,Max).

max([N],N) :- !.
max([N|R],Max) :-
        max(R,Max2),
        max3(N,Max2,Max).

max3(N,Max2,N) :- N > Max2,!.
max3(N,Max2,Max2).

回答6:

To have the length of longest list:

%sample: longest([[2,1,3],[7,5],[1,8,2,3,1],[2,7,1,4]],L,LEN).

longest([L], L, _) :-
   !.
longest([H|T], H, _) :-
   length(H, N),
   longest(T, X, N),
   length(X, M),
   N > M,
   !.
longest([_|T], X, LEN) :-
   length(X, LEN),
   longest(T, X, LEN),
   !.