4

いくつかの簡単な演習を実行しようとして、プロローグを紹介されたばかりですが、私はこれに固執しています。入力リストのすべてのサブリストを出力するプログラムを作成しようとしています。各サブリストの長さは1より大きいため、より大きなサブリストに拡張することはできません。また、サブリストのリストの開始位置も出力されます。したがって、サンプル出力は次のようになります。

| ?- plateau([a,a,b,2,2,2,a+1,a+1,s(1,2)], I, Len).
    I = 1,
    Len = 2 ? ;
    I = 4,
    Len = 3 ? ;
    I = 7,
    Len = 2 ? ;
    no

私はまだ宣言的なこと全体にかなり混乱していて、命令モードから切り替えるのに多くの問題を抱えています。私は自分のプログラムに次のようなことをさせたいと思っています

program([H|T],I,L):-
    T = [H1|T1] %split the tail
    ([H] = [H1] -> Count is Count+1, program(T,I,Count) 
     %if First element = second element, recurse with new values
    ; length(T,Spot), 
      %get the spot where you are in the list, so we know where sublist starts
      program(T,Spot,L) %run again, from tail, since sublist didn't have another  element?
program([],I,L). %terminate when entire list has been run through?

いくつかの理由で私が言えることから、これは機能していません。'count'をリセットしないので、すべてのサブリストの値を合計すると、多分？これを回避する方法はありますか？私のベースケースも私が望むものではないかもしれません-私はそれが本当にどうあるべきかわからないだけですか？私はおそらく他のものも見逃しています...どんな助けでも大歓迎です！：） ありがとう！

4

5 に答える 5

7

プログラムは、多くの異なる問題を1つの述語に結合します。それらを少し分けてみましょう。また、同じ要素を含む2つ以上の要素の最大サブリストを検索していると仮定します。

必要なものの概算から始めましょう：サブリストの識別。これが広すぎることを心配しないでください。後で改良します。この目的のためにDCGを使用します。非終端記号seq//1は、任意のシーケンスを表します。

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

これは非常に便利な非終端記号です！

？-フレーズ（（seq（プレフィックス）、seq（サブリスト）、seq（ポストフィックス））、
      [a、a、b、2,2,2、a + 1、a + 1、s（1,2）]）。
プレフィックス=サブリスト、サブリスト= []、
接尾辞=[a、a、b、2,2,2、a + 1、a + 1、s（1,2）];
プレフィックス=[]、
サブリスト= "a"、
接尾辞=[a、b、2,2,2、a + 1、a + 1、s（1,2）]..。

両方の答えは期待されていません。長さが2以上のサブリストのみが必要なので、その定義を少し制限する必要があります。Sublistたとえば、少なくとも2つの要素が含まれている必要があることを要求します。それはSublist = [_,_|_]です。

？-サブリスト= [_、_ | _]、
   フレーズ（（seq（プレフィックス）、seq（サブリスト）、seq（ポストフィックス））、
      [a、a、b、2,2,2、a + 1、a + 1、s（1,2）]）。
サブリスト="aa"、
プレフィックス=[]、
後置=[b、2,2,2、a + 1、a + 1、s（1,2）];
サブリスト="aab"、
プレフィックス=[]、
接尾辞=[2,2,2、a + 1、a + 1、s（1,2）]..。

最初の答えは、私たちが探しているサブリストを示しています。しかし、2番目はまだ正しくありません。サブリストのすべての要素が等しくなければなりません。最も簡単な方法は、以下を使用することmaplist/2です。

？-maplist（=（_）、Es）。
Es = [];
Es = [_G221];
Es = [_G221、_G221];
Es = [_G221、_G221、_G221]

その要件を述べることができる場所がいくつかあります。私はそれを可能な限り早い場所に置きます：

？-サブリスト= [_、_ | _]、
        フレーズ（（seq（プレフィックス）、
                 seq（Sublist）、{maplist（=（_）、Sublist）}、
                 seq（Postfix））、
           [a、a、b、2,2,2、a + 1、a + 1、s（1,2）]）。
サブリスト="aa"、
プレフィックス=[]、
後置=[b、2,2,2、a + 1、a + 1、s（1,2）];
サブリスト=[2,2]、
プレフィックス="aab"、
接尾辞=[2、a + 1、a + 1、s（1,2）];
サブリスト=[2,2,2]、
プレフィックス="aab"、
接尾辞=[a+ 1、a + 1、s（1,2）];
サブリスト=[2,2]、
プレフィックス=[a、a、b、2]、
接尾辞=[a+ 1、a + 1、s（1,2）];
サブリスト=[a+ 1、a + 1]、
プレフィックス=[a、a、b、2,2,2]、
後置=[s（1,2）];
false。

そのため、すべてのサブリストに同じ要素が含まれるようになりました。残念ながら、両方[2,2]と[2,2,2]サブリストを取得します。最大のサブリストのみが必要です。では、最大サブリストとはどのように説明できるでしょうか。

1つの方法は、サブリストの前を確認することです。サブリストにまったく同じ要素があってはなりません。したがって、前に何も（イプシロン）ないか、または私たちとは異なる要素で終わるシーケンスがあります。

difel(_E,[]).
difel(E, Es) :- dif(E,F), phrase((seq(_), [F]), Es).

？-サブリスト= [_、_ | _]、
   フレーズ（（seq（プレフィックス）、{difel（E、プレフィックス）}、
            seq（Sublist）、{maplist（=（E）、Sublist）}、
            seq（Postfix））、
      [a、a、b、2,2,2、a + 1、a + 1、s（1,2）]）。
サブリスト="aa"、
プレフィックス=[]、
E = a、
後置=[b、2,2,2、a + 1、a + 1、s（1,2）];
サブリスト=[2,2]、
プレフィックス="aab"、
E = 2、
接尾辞=[2、a + 1、a + 1、s（1,2）];
サブリスト=[2,2,2]、
プレフィックス="aab"、
E = 2、
接尾辞=[a+ 1、a + 1、s（1,2）];
サブリスト=[a+ 1、a + 1]、
プレフィックス=[a、a、b、2,2,2]、
E = a + 1、
後置=[s（1,2）];
false。

間違った答えが1つ少なくなります。最後にまだ1つ潜んでいます。

？-サブリスト= [_、_ | _]、
   フレーズ（（seq（プレフィックス）、{difel（E、プレフィックス）}、
            seq（Sublist）、{maplist（=（E）、Sublist）}、
            （[] | [F]、{dif（E、F）}、seq（_）））、
      [a、a、b、2,2,2、a + 1、a + 1、s（1,2）]）。
サブリスト="aa"、
プレフィックス=[]、
E = a、
F = b;
サブリスト=[2,2,2]、
プレフィックス="aab"、
E = 2、
F = a + 1;
サブリスト=[a+ 1、a + 1]、
プレフィックス=[a、a、b、2,2,2]、
E = a + 1、
F = s（1,2）;
false。

それはあなたが望んでいたものではありません：あなたは単に長さを望んでいました。このために、を追加しlength([_|Prefix],I), length(Sublist,Len)ます。

したがって、最終的な定義は次のとおりです。

高原（Xs、I、Len）：-
   サブリスト=[_、_ | _]、
   フレーズ（（seq（プレフィックス）、{difel（E、プレフィックス）}、
            seq（Sublist）、{maplist（=（E）、Sublist）}、
            （[] | [F]、{dif（E、F）}、seq（_）））、
      Xs）、
   長さ（[_ |プレフィックス]、I）、
   length（Sublist、Len）。
于 2012-03-13T14:43:05.470 に答える
2

ここには非常に多くの複雑な答えがあります。DCGまたは多くの組み込みを使用しないこれを検討してください（おそらく初心者にとってはより簡単です）：

plateau([X|Xs], I, L) :-
    plateau(Xs, 1-1-X, I, L).

plateau([X1|Xs], I0-L0-X0, I, L) :-
    X0 == X1, !,
    NL0 is L0 + 1,
    plateau(Xs, I0-NL0-X0, I, L).

plateau(_, I-L-_, I, L) :-
    L > 1.

plateau([X|Xs], I0-L0-_, I, L) :-
    NI is I0 + L0,
    plateau(Xs, NI-1-X, I, L).

最初の句は、用語として--(index)タプルを累積する呼び出しを設定します。(length)(sublist element)

次の句はlength、次のリストelementが同じである場合にインクリメントします（インデックスは変更されないことに注意してください）。

3番目の句は、サブリスト要素の実行が壊れているかどうかをテストするときに2番目の句が失敗した場合にのみ呼び出され（カットのため）、実行のがであった!場合は解を返します。length> 1

最後の節は、Prologが最後の実行から検索をバックトラックして再開できるようにします。

編集： gusbroのソリューションは実際にはこれに非常に近いです...+1。

于 2012-03-15T22:12:31.443 に答える
1

あなたはこのようなことをすることができます：

plateau([Item|Tail], I, Len):-
  plateau(Tail, 1, Item, 1, I, Len).

plateau(List, From, NItem, Len, From, Len):-
  (List=[Item|_] -> (Item\=NItem;var(Item)); List = []),
  Len > 1.
plateau([Item|Tail], IFrom, Item, ILen, From, Len):-
  MLen is ILen + 1,
  plateau(Tail, IFrom, Item, MLen, From, Len).
plateau([Item|Tail], IFrom, OItem, ILen, From, Len):-
  OItem \= Item,
  NFrom is IFrom + ILen,
  plateau(Tail, NFrom, Item, 1, From, Len).

プラトー/6の最初の節は、サブリストの終了を扱います。アイテムが探しているものと異なるか、リストの最後に到達したかのいずれかです。その場合、現在の長さが1より大きい場合にのみ続行します。

2番目の句は、リスト内の要素とまだ一致している場合の再帰ステップを扱います。現在のサブリストのカウンターに1つ追加するだけで、再帰を実行します。

最後の句は、リストで見つかった新しい（異なる）アイテムの場合を扱い、カウンターをリセットして再帰を実行します。

于 2012-03-13T14:32:12.153 に答える
1

nth1 / 3ビルトインを使用してみましたが、動作させるのにさらに問題がありました...とにかく、ここに別の実装があります：

plateau(L, I, Len) :-
    plateau(L, 1, I, Len).
plateau(L, P, I, Len) :-
    nth1(P, L, E),
    skipseq(P, L, E, J),
    (   J > P,
        Len is J - P + 1,
        I is P
    ;   Q is J + 1,
        plateau(L, Q, I, Len)
    ).

% get the index J of last element E (after I)
skipseq(I, L, E, J) :-
    T is I + 1,
    nth1(T, L, E),
    !, skipseq(T, L, E, J).
skipseq(I, _, _, I).

テスト：

[debug]  ?- plateau([a,x,x,x,u,u,h,w],I,N).
I = 2,
N = 3 ;
I = 5,
N = 2 ;
false.
于 2012-03-13T17:39:30.317 に答える
1

これは単純明快です。1から数えます。プラトーは、少なくとも2つの長さの等しい要素の最大のサブシーケンスです。リストに沿って進みます。それを書き留めてください：

plateau(L,I,N):- plateau(L,1,I,N).                     % count from 1

plateau([A,A|B],I1,I,N):- !, more_elts(A,B,2,K,C),     % two equals, or more
    (I is I1, N is K ; plateau(C,I1+K,I,N)).
plateau([_|B],I1,I,N):- plateau(B,I1+1,I,N).           % move along the list

more_elts(A,[A|B],I,K,C):- !, more_elts(A,B,I+1,K,C).
more_elts(_,B,I,I,B).

更新：これは、入力リストのすべての要素がであると想定していますnonvar/1。ここで入力リストの要素としてインスタンス化されていない変数があると、「サブリスト」の概念がトリッキーで曖昧になります。たとえば、のサブリストは[a,X,b,b]何ですか？両方を同じ入力リストのサブリストにすることは[a,a]できます（これは、スピンの観測可能な値、状態の重ね合わせなどを何とか思い出させます...スピン観測の方向を選択すると、それはもう変更できません...「測定」と量子力学に関するすべての話を参照してください。sokuza-kanren.scm （ここにそのリンクがあります））[b,b,b]

于 2012-03-16T10:50:13.440 に答える