Prolog

Question

我想在 Prolog 中解决以下练习：

For a list of integers Zs, max_sequence(Zs,Xs) finds a longest increasing subsequence Xs.

示例查询：

?- max_sequence([1,2,1,2,3,4,2,1,2,1],Xs).
Xs = [1,2,3,4].                                     % expected result

?- max_sequence([1,2,1,2,3,4,2,1,6,7,7,2,1,8],Xs).
Xs = [1,2,3,4,6,7,8].                               % expected result

我不明白为什么...但是我的代码是错误的，结果总是false。

max_sequence(L,R) :-
    cresc(L,[],R).

cresc([],[],[]).
cresc([H|T],C,[H|C]) :-
    maxList(H,C),
    \+ member(H,C),
    cresc(T,C,C).
cresc([H|T],C,C) :-
    member(H,C),
    cresc(T,C,C).       
cresc([H|T],C,C) :-
    \+ maxList(H,C),
    cresc(T,C,C).   

maxList(_,[]).
maxList(N, [H|T]) :-
    N>H,
    maxList(N,T).

我想知道我处理问题的方法是否正确。感谢您的帮助！

Answer 1

我完全无法理解你的方法，但是在swi-prolog中使用Trace命令你可以看到你的程序一步步执行，看看它在哪里失败了。试试吧，你会发现你的代码有什么问题。

无论如何，这可能是一个可能的解决方案：从列表的第一个元素开始，您应该简单地收集一个列表，直到元素增加，同时保持该子列表的长度，这是第一个候选者。然后再次开始收集新列表及其长度，如果比候选者长，则切换它们，依此类推。在这里你可以找到代码：max_seqs，第一部分。

Answer 2

TL;DR: 高层次解决问题：惯用思维；不要重新发明轮子:)

使用clpfd!

:- use_module(library(clpfd)).

我们采取以下两个步骤：

我们首先使用 meta-predicate splitlistIfAdj/3 together with (#>=)/3:

?- splitlistIfAdj(#>=,[1,2,2,2,1,2,3,4,2,1,3,5,7,1],Zss).
Zss = [[1,2],[2],[2],[1,2,3,4],[2],[1,3,5,7],[1]].

我们只对最大尺寸的子列表感兴趣。 max_of_by/3 可以排除所有其他的：

?- max_of_by(Xs,[[1,2],[2],[2],[1,2,3,4],[2],[1,3,5,7],[1]],length).
  Xs = [1,2,3,4]
; Xs = [1,3,5,7].

就是这样！让我们把它放在一起定义 list_longest_ascending_sublist/2:

list_longest_ascending_sublist(Xs,Zs) :-
   splitlistAdjIf(#>=,Xs,Yss),
   max_of_by(Zs,Yss,length).

示例查询：

?- list_longest_ascending_sublist([1,2,2,2,1,2,3,4,2,1,3,5,7,1],Zs).
  Zs = [1,2,3,4]
; Zs = [1,3,5,7].

?- list_longest_ascending_sublist([1,2,2,3,4,5,6,2,1,2,3,4,2,1,3,5,7,1],Zs).
Zs = [2,3,4,5,6].

Prolog - 寻找最长的递增子序列

Prolog - Finding the longest increasing subsequence

list

clpfd