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]から検索を再開する必要はありません: シーケンスは で壊れます。から検索を続行します。bde

そのため、検索中にいくつかの追加情報を持ち歩くだけです。現在およびこれまでに勝利したサブシーケンス。そしてそれらの長さ。

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を微調整して、より効率的なソリューションにすることもできます。勝ったサブシーケンスを 1 つだけ維持する代わりに、入力リストに沿って進行するすべての関連する可能性を維持します。

于 2013-03-27T11:01:56.480 に答える
0

好奇心から、最長増加サブシーケンスを見つけるためにプロローグでこのようなことを実現することは可能でしょうか:

  • リストのすべてのサブセットを見つける
  • これらのサブセットのどれが増加しているかがわかります
  • そして、最長を検索します

可能であれば、どうすれば Prolog でそれを行うことができますか?

于 2013-04-06T09:12:42.137 に答える