Prolog List Plateau.
-
13-12-2019 - |
質問
は、簡単な演習を受けているとしている、Prologに紹介されましたが、私はこれに立ち往生しています。 入力リストのすべてのサブリストを出力するプログラムを作成しようとしています。各サブリストは長さ> 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'をリセットしません、それでそれはすべてのサブリストの値を一緒に集まっているかもしれません。これを回避する方法はありますか?私の基本ケースも私が欲しいものではありません - 私はそれが本当に何があるべきかわからないのですか?私はおそらく他のものを見逃しています...あらゆる助けが大いに感謝されています!:) ありがとう!
解決
ここでは非常に複雑な答えがたくさんあります。DCGSまたは多くの組み込みを使用しない(おそらく初心者にとってより簡単な):
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).
.
first句は、(index)
-GeneraCodeTagCode-(length)
Tupleを累積するコールを用語として設定します。
Next句は、次のリスト(sublist element)
が同じ場合はlength
をインクリメントします(索引は変更されません)。
3番目の句は、sublist要素の実行が壊れたときに(Cut element
のため)が壊れたときに2番目の句が失敗した場合にのみ呼び出され、実行の!
がlength
である場合のソリューションIFFを返します。
最後の節を使用すると、Prologが最後の実行から検索を再開します。
編集: gusbroの解決策は実際にはこの1つに非常に近いです... + 1。
他のヒント
あなたのプログラムはさまざまな問題を1つの述語にまとめました。それらを少し分離しようとしましょう。また、同一の要素を含む2つ以上の要素の最大サブリストを検索していると思います。
あなたが望むものの近似から始めましょう:サブリストの識別。これが幅すぎることであることを心配しないでください、後でそれを洗練します。この目的のためにDCGSを使用します。非端子seq//1
は任意のシーケンスを記述します。
seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).
.
これは非常に便利な非端末です!
?- phrase((seq(Prefix),seq(Sublist),seq(Postfix)), [a,a,b,2,2,2,a+1,a+1,s(1,2)]). Prefix = Sublist, Sublist = [], Postfix = [a,a,b,2,2,2,a+1,a+1,s(1,2)] ; Prefix = [], Sublist = "a", Postfix = [a,b,2,2,2,a+1,a+1,s(1,2)] ....
両方の答えは予想されていないので、長さ2以上のサブリストを望むので、その定義を少し制限する必要があります。 Sublist
が少なくとも2つの要素を含むべきであることを要求することによって言う。それはSublist = [_,_|_]
です。
?- Sublist = [_,_|_], phrase((seq(Prefix),seq(Sublist),seq(Postfix)), [a,a,b,2,2,2,a+1,a+1,s(1,2)]). Sublist = "aa", Prefix = [], Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ; Sublist = "aab", Prefix = [], Postfix = [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].
その要件を述べることができるいくつかの場所があります。私は可能な限り早い場所にそれを置きます:
?- Sublist = [_,_|_], phrase(( seq(Prefix), seq(Sublist),{maplist(=(_),Sublist)}, seq(Postfix)), [a,a,b,2,2,2,a+1,a+1,s(1,2)]). Sublist = "aa", Prefix = [], Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ; Sublist = [2,2], Prefix = "aab", Postfix = [2,a+1,a+1,s(1,2)] ; Sublist = [2,2,2], Prefix = "aab", Postfix = [a+1,a+1,s(1,2)] ; Sublist = [2,2], Prefix = [a,a,b,2], Postfix = [a+1,a+1,s(1,2)] ; Sublist = [a+1,a+1], Prefix = [a,a,b,2,2,2], Postfix = [s(1,2)] ; false..
今や、すべてのサブリストには同一の要素が含まれています。 AlAs、[2,2]
と[2,2,2]
の両方がサブリストとして取得されます。最大サブリストのみが欲しいのです。それでは、最大のサブリストが何であるかをどのように説明できますか?
一方向は私たちのサブリストの前に見えることです。したがって、前方に(ε)、または私たちのものとは異なる要素で終わるシーケンスのいずれか。
difel(_E,[]).
difel(E, Es) :- dif(E,F), phrase((seq(_), [F]), Es).
.
?- Sublist = [_,_|_], phrase(( seq(Prefix),{difel(E,Prefix)}, seq(Sublist),{maplist(=(E),Sublist)}, seq(Postfix)), [a,a,b,2,2,2,a+1,a+1,s(1,2)]). Sublist = "aa", Prefix = [], E = a, Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ; Sublist = [2,2], Prefix = "aab", E = 2, Postfix = [2,a+1,a+1,s(1,2)] ; Sublist = [2,2,2], Prefix = "aab", E = 2, Postfix = [a+1,a+1,s(1,2)] ; Sublist = [a+1,a+1], Prefix = [a,a,b,2,2,2], E = a+1, Postfix = [s(1,2)] ; false..
誤った回答が少ない。最後にまだ潜んでいます。
?- Sublist = [_,_|_], phrase(( seq(Prefix),{difel(E,Prefix)}, seq(Sublist),{maplist(=(E),Sublist)}, ( [] | [F],{dif(E,F)},seq(_) ) ), [a,a,b,2,2,2,a+1,a+1,s(1,2)]). Sublist = "aa", Prefix = [], E = a, F = b ; Sublist = [2,2,2], Prefix = "aab", E = 2, F = a+1 ; Sublist = [a+1,a+1], Prefix = [a,a,b,2,2,2], E = a+1, F = s(1,2) ; false..
それはあなたが望むものだけではありません:あなたは単に長さを望んでいました。このために、length([_|Prefix],I), length(Sublist,Len)
を追加します。
だからここに最終的な定義があります:
plateau(Xs, I, Len) :- Sublist = [_,_|_], phrase(( seq(Prefix),{difel(E,Prefix)}, seq(Sublist),{maplist(=(E),Sublist)}, ( [] | [F],{dif(E,F)},seq(_) ) ), Xs), length([_|Prefix],I), length(Sublist,Len)..
私は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.
. あなたはこのようなことができる:
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つを追加し、再帰を行います。
最後の句は、リストにある新しい(異なる)項目の場合を扱い、カウンタをリセットして再帰を行います。
これは簡単で簡単です。 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).
.
update: 入力リストのすべての要素がnonvar/1
であると仮定します。入力リストの要素として非インスタンス化されていない変数を持つと、「サブリスト」の概念と曖昧さがあります。例えば、[a,X,b,b]
のサブリストは何ですか? [a,a]
と[b,b,b]
の両方が同じ入力リストのサブライストですか? (これは、スピンの観察可能な値、状態の重ね合わせなどをどう思います...スピン観察の方向が選択されると、もう変更することはできません... CF.すべての話「測定」についてのすべての話 sokuza-kanren.scm (リンクここ))