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

Question

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.

Can you write a 3-place predicate that compares two lists and "returns" the one that is longer? — Kaarel, Nov 02 '09 at 11:23

score 8 · Accepted Answer · answered Nov 02 '09 at 11:34

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

I'm not sure how this would be if the number are actual lists. Because the head of the list would be a a list. — Algific, Nov 02 '09 at 12:36
select_element/3 does not care what is the nature (e.g. atomic or list) of the list elements. Everything depends on the predicate that you have to write (get_longer_list/3). — Kaarel, Nov 02 '09 at 13:44

score 3 · Answer 2 · edited Dec 05 '15 at 17:03

3

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!

edited Dec 05 '15 at 17:03

repeat

18,496
4
54
166

answered Nov 05 '09 at 19:17

Juanjo Conti

28,823
42
111
133

Of course, you can also validate that the manipulated objects are actually lists. – Juanjo Conti Nov 05 '09 at 19:21
3

The complexity of your solution is O(n^2). That's too much for a simple problem like this... – Kaarel Nov 09 '09 at 11:51
The goal `longest([[1],[2]],[1])` fails. It *should* succeed! – repeat Aug 06 '15 at 09:22

score 2 · Answer 3 · edited May 23 '17 at 11:52

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

score 2 · Answer 4 · answered Dec 05 '15 at 16:16

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

s(X) for returning **all** lists of maximum length. – repeat Dec 05 '15 at 16:53 — repeat, Dec 05 '15 at 16:53

score 0 · Answer 5 · edited Dec 05 '15 at 17:01

0

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

edited Dec 05 '15 at 17:01

repeat

18,496
4
54
166

answered Apr 29 '11 at 13:26

Aleg

23
1
5

score 0 · Answer 6 · answered Apr 29 '11 at 17:36


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

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

6 Answers6

Linked