Prolog

Question

我正在尝试获取列表中最长的子列表。我需要一个递归搜索列表列表并确定哪个列表长度最长的规则。

例如：
输入：[[1],[1,2],[],[1,2,3,4],[5,6]]
输出：[1,2,3,4]

这是我目前拥有的：

max([H|T], Path, Length) :-
  length(H, L),
  (L @> Length -> 
  max(T, H, L) ;
  max(T, Path, Length) ).

我希望max()这样工作：

? max([[1],[1,2],[],[1,2,3,4],[5,6]], Path, Distance).
Path = [1,2,3,4]
Distance = 4

当我运行跟踪时，这是输出：

{trace}
| ?- max([[1],[1,2],[],[1,2,3,4],[5,6]], Path, Distance).
      1    1  Call: max([[1],[1,2],[],[1,2,3,4],[5,6]],_307,_308) ? 
      2    2  Call: length([1],_387) ? 
      2    2  Exit: length([1],1) ? 
      3    2  Call: 1@>_308 ? 
      3    2  Exit: 1@>_308 ? 
      4    2  Call: max([[1,2],[],[1,2,3,4],[5,6]],[1],1) ? 
      5    3  Call: length([1,2],_462) ? 
      5    3  Exit: length([1,2],2) ? 
      6    3  Call: 2@>1 ? 
      6    3  Exit: 2@>1 ? 
      7    3  Call: max([[],[1,2,3,4],[5,6]],[1,2],2) ? 
      8    4  Call: length([],_537) ? 
      8    4  Exit: length([],0) ? 
      9    4  Call: 0@>2 ? 
      9    4  Fail: 0@>2 ? 
      9    4  Call: max([[1,2,3,4],[5,6]],[1,2],2) ? 
     10    5  Call: length([1,2,3,4],_587) ? 
     10    5  Exit: length([1,2,3,4],4) ? 
     11    5  Call: 4@>2 ? 
     11    5  Exit: 4@>2 ? 
     12    5  Call: max([[5,6]],[1,2,3,4],4) ? 
     13    6  Call: length([5,6],_662) ? 
     13    6  Exit: length([5,6],2) ? 
     14    6  Call: 2@>4 ? 
     14    6  Fail: 2@>4 ? 
     14    6  Call: max([],[1,2,3,4],4) ? 
     14    6  Fail: max([],[1,2,3,4],4) ? 
     12    5  Fail: max([[5,6]],[1,2,3,4],4) ? 
      9    4  Fail: max([[1,2,3,4],[5,6]],[1,2],2) ? 
      7    3  Fail: max([[],[1,2,3,4],[5,6]],[1,2],2) ? 
      4    2  Fail: max([[1,2],[],[1,2,3,4],[5,6]],[1],1) ? 
      1    1  Fail: max([[1],[1,2],[],[1,2,3,4],[5,6]],_307,_308) ? 

(2 ms) no

我认为问题在于我没有处理空集“[]”的出现。但是，我尝试了几种不同的方法，但无法获得所需的输出。

Answer 1

你应该定义循环结束子句，返回时需要多一个参数

max([], _, Length, Length).
max([H|T], Path, Length, RetLength) :-
  length(H, L),
  ( L @> Length -> 
    max(T, H, L,RetLength) ;
    max(T, Path, Length,RetLength) 
  ).

测试：

?- max([[1],[1,2],[],[1,2,3,4],[5,6]], Path, Distance,Len).
Len = 4.

Prolog - 列表中最长的子列表

Prolog - longest sublist within a list

recursion

list

longest-path