Как найти самый длинный список в списке списков?

Question

У меня есть список списков, и мне нужно найти самый длинный из них. Если их больше одной одинаковой длины, то они возвращаются. Благодарю.

Answer 1

Вот общий предикат, который сканирует список, чтобы найти один член, определенный заданной целью.

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

Допустим, вы определить предикат

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

Теперь вы можете выполнить:

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

Selected = 10 

Так все, что вам нужно сделать сейчас, это определить предикат get_longer_list(L1, L2, L), и использовать его вместо от get_bigger_number/3.

Конечно, использование общего предиката, такого как select_element/3, может быть не очень эффективным. Например, вам следует попытаться избежать вычисления длины одного и того же списка несколько раз, потому что этот расчет медленный в Prolog (по крайней мере, если он реализован в Prolog стандартным образом).

Answer 2

Пожалуйста, рассмотрите мой подход.

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

Тогда вы можете обращаться к нему:

?- 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] ; 

здоровается!

Answer 3

Чтобы иметь длину самого длинного списка:

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

Answer 4

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

Answer 5

Определим longest/2 на основе meta-predicatemax_of_by/3 используется в тандеме с length/2:

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

Примеры запросов:

?- 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 

Answer 6

Вот еще один эффективный и понятный подход. Идея состоит в том, чтобы найти длины всех списков в списке, используйте max_list, чтобы получить длину самого длинного списка, а затем найдите список, который длинный. Это имеет то преимущество, что оно вернет все списки самой длинной длины.

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