从列表列表中获取最短列表

Question

我正在处理一个项目，但我遇到了一个谓词问题，该谓词需要获取列表列表中所有列表的最短列表。假设我们有以下列表：

Listoflists = [[u,f,c,x,e], [a,v,c], [r,j,[m], [a,l,c,p]]

所以我想要的是一个谓词 shortest/2，当被问到时 shortest(Listoflists, A) 回答 A = [m]。问题是我不能使用 maplist/3 因为项目的限制，这就是为什么我问自己而不是使用别人的问题。我已经看到 keysort/2 在这些情况下很有用，但要使它起作用，我需要一个成对的列表 (list, listlength)（或类似的东西，我不确定）而且我不知道如何得到它。如果对您有帮助，我正在 Ciao Prolog 工作，谢谢您的回答。

Answer 1

您可以通过创建另一个谓词（我在这里称之为 shorter）然后在 shortest 中使用它来实现此目的：

shorter(_, [], []) :- !.
shorter([], _, []).
shorter([A | R1], [_ | R2], [A | R1]) :- shorter(R1, R2, R1), !.
shorter([_ | R1], [B | R2], [B | R2]) :- shorter(R1, R2, R2).

shortest([], []).
shortest([A], A) :- !.
shortest([A, B | R], X) :- shorter(A, B, T), shortest([T | R], X).

Answer 2

如果库（aggregate）没有被禁止，那么一个简单的解决方案是

shortest(L,S) :- aggregate(min(C,E),(member(E,L),length(E,C)),min(_,S)).

library(aggregate) 很强大，值得学习，但是你的问题可以用setof/3轻松解决。想试一试吗？让我知道...

编辑

使用标准内置setof/3，代码类似，使用member/2访问每个列表元素并获取其长度，然后用于排序（在setof/3 ) 或最小化 (in aggregate/3).

shortest(L,S) :- setof((C,E),(member(E,L),length(E,C)),[(_,S)|_]).

这适用于特定情况，但 library(aggregate) 更通用，所以我更喜欢在...之前显示...

Answer 3

我们可以采用生成方法，

%% L must be uninstantiated
shortest( LS, L ) :-
  length( L, _),      % length of L is N=0 or N+1
  member( L, LS).     % L is a member of LS

生成的第一个解决方案将是列表中最短的（最左边的）LS。因此，如果需要，请添加剪辑 !。

Answer 4

你会做这样的事:

shortest( [A], A ). % lists of length 1 are easy
shortest( [A,B|C], S ) :-
    shortest( [B|C], D ) ,
    shorter( A, D, S ).

shorter( A , B, C ) :-
    length(A,La),
    length(B,Lb),
    (   La < Lb ->  C = A ; C = B ).

但是它留下了悬而未决的选择点，它的计算成本很高（每次调用都要遍历两次列表），并且它会在调用堆栈上推送很多东西：给定足够长的列表，你会得到堆栈溢出。

不过，稍微重构一下，我们可以对此进行改进。下面没有留下开放的选择点，它只计算每个子列表的长度一次，而且它是尾递归的，所以不会增加堆栈。

shortest( [A     ] , A ) .
shortest( [A,B|Cs] , S ) :-
    length(A,La),
    shortest( [B|Cs], La:A, S ).

shortest( []     , _:S  , S ).
shortest( [A|Bs] , Lc:C , S ) :-
    length(A,La),
    ( La < Lc ->  X = La:A ; X = Lc:C ),
    shortest(Bs,X,S).

Answer 5

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

shortest([L], L).
shortest([L1,L2|R], S) :- min(L1, L2, L), shortest([L|R], S).

min(L1, L2, S) :- min(L1, L2, L1, L2, S).

min([], _, L1, _, L1).
min(_, [], _, L2, L2).
min([_|R1], [_|R2], L1, L2, S) :- min(R1, R2, L1, L2, S).

这个解决方案的优点是：

它避免了使用条件构造 (IF -> THEN ; ELSE)（或剪切）的需要。
它避免了多次比较两个列表以获得最小长度的列表（与参数的顺序无关）。
它避免了按长度对列表进行排序的需要。
它避免了使用特殊库的需要。
当存在多个最小长度的列表时，它的工作方式不确定。

这里有一个例子：

?- shortest([[a,b,c,d], [e,f,g], [h,i], [j], [k], [l,m,n,o]],S).
S = [j] ;
S = [k] ;
false.

从列表列表中获取最短列表

Getting the shortest list from a list of lists

prolog