1

我想在 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).

谁能帮我找到最长的增加子集？

4

2 回答 2

1

你的意思[1,3,5,6,7]是回答[4,1,3,8,9,5,6,7]？IOW，您真的是指子集，还是只是子列表，即列表的连续部分？

如果是后者，则不需要子集。搜索是线性的。如果在一个列表中[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.

也许您的意思是最长的保序子序列，即允许它是不连续的。然后，您可以收集您的subsetwithfindall或类似谓词的所有解决方案，并分析这些结果：

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或者，可以调整线性搜索以获得更有效的解决方案。它不会只保留一个获胜子序列，而是会在输入列表中保留所有相关的可能性。

于 2013-03-27T11:01:56.480 回答
0

只是出于好奇，是否有可能在 prolog 中实现类似的东西来寻找最长的递增子序列：

  • 您找到列表的所有子集
  • 比你发现的，这些子集中的哪一个在增加
  • 然后你搜索最长的

如果可能的话，我怎么能在 Prolog 中做到这一点？

于 2013-04-06T09:12:42.137 回答