最长递增子集序言(Longest increasing subset Prolog)

我想创建Prolog的条目相关的关键字列表的最长递增子集。例如，输入的[3,1,2]列表和输出是[1,2]，

?- subset([3,1,2], X).
X = [1,2]

我有代码显示了这个列表的所有子集：

subset([],[]).
subset([_|X],Y):-subset(X,Y).
subset([A|X],[A|Y]):-subset(X,Y).

谁能帮我找到刚才最长递增子集？

Answer 1:

你的意思是[1,3,5,6,7]要的答案[4,1,3,8,9,5,6,7] ？督察，你真正的意思的子集，或者只是子列表，即列表中的连续部分？

如果是后者的话，您将不需要的子集。搜索是线性的。如果在列表[a,b,c,d,e,f]你发现d > e和递增序列[a,b,c,d]停止，你不需要重新启动从搜索b现在中的序列仍然会断裂d 。你只会继续从搜索e 。

所以，我们只随身携带一些额外的信息的搜索，即中。当前和中标那么远的子序列。其长度。

longest_incr([],0-[]).
longest_incr([A|B],RL-R):-                  % R is the result, of length RL
    longest_aux(B,[],0, [A],1, RL-R). 

longest_aux([],   Win,N, Curr,K, RL-R):- 
    ( K>N -> RL=K, reverse(Curr,R) ; RL=N, reverse(Win,R) ).
longest_aux([A|B],Win,N, Curr,K, RL-R):- Curr = [X|_], L is K,
    ( A>X -> longest_aux(B,Win, N, [A|Curr],L+1,RL-R)    % keep adding
    ; L>N -> longest_aux(B,Curr,K, [A],     1,  RL-R)    % switch the winner
    ;        longest_aux(B,Win, N, [A],     1,  RL-R)    % winner unbeaten 
    ).

如果OTOH你真的需要最长的子集......有一个矛盾存在。一组可以有它的元素重新排列，所以给定的列表中最长的子集将是

longset_subset(L,R):- sort(L,S), R=S.

也许你的意思是最长的保序子序列，也就是说，它允许是不连续的。然后你就可以收集所有的解决方案，你的subset用findall或类似的断言，并分析这些结果：

longest_subseq(L,R):- 
    findall( S, subset(L,S), X),
    maplist( longest_incr, X, Y),
    keysort( Y, Z), 
    last( Z, _Len-R).

上面有很多在它的冗余。我们可以尝试通过只允许增加子序列，以提高其效率：

incr_subseq([],[]).
incr_subseq([_|X],Y):- incr_subseq(X,Y).
incr_subseq([A|X],[A|Y]):- incr_subseq(X,Y), ( Y=[] ; Y=[B|_], A<B).

现在，所有通过上述谓词中发现的子序列将越来越大，因此我们可以只取它们的length S：

lenlist(List,Len-List) :- length(List,Len).
longest_subseq(L,R):- 
    findall( S, incr_subseq(L,S), X),
    maplist( lenlist, X, Y),
    keysort( Y, Z), 
    last( Z, _Len-R).

或者，线性搜索longest_incr可以调整了一个更有效的解决方案。相反，保持只有一个获胜子序列，因为它沿输入不胜枚举，将维持所有相关的可能性。

Answer 2:

只是出于好奇，它会在序言中可以实现这样的寻找最长递增子：