Prolog：リスト内の2つの要素が等しく発生しているかどうかを調べる

Question

私はPrologを初めて使う人でありネイティブスピーカーではないので、わからないのは残念です。

私の質問は、リストからaとbが同じように表示される場合はどうすれば見つけることができますか？

たとえば、[a,a,b,b]は私にtrueを与えますが、一方が他方よりも多く現われる場合はfalseとなります。例：[a,a,a,b,b]。

誰でも教えてください。これは私がこれまで持っていたものであり、間違っていることを知っていますが、私は試しています。

count(N,[],0). 
count(N,[N|T],U) :- 
    !, 
    count(N,T,U1), 
    U is U1+1. 
count(N,[H|T],U) :- 
    count(N,T,U). 

occurrences([],[]). 
occurrences([H|T],[[H,X]|Y]) :- 
    count(H,[H|T],X), 
    occurrences(T1,Y). 

Answer 1

訪問中に、リストの末尾に一致する要素を選択することができます。

再帰ベースのケースは、あなたが考えることができる最も単純なものになります... とselect/3は、あなたの問題に本当にコンパクトなソリューションを可能にする組み込みです。

編集

だけでなく、コードは簡単です...

occurrences([],[]). 
occurrences([H|T],R) :- select(H,T,U), occurrences(U,R). 

注：成功の上に、Rは、空のリスト

Answer 2

になります1つだけのリストを持っているので、最初にあなたのパターンマッチングは失敗します。私はこれを試してみて、どんな説明を加えていないので、あなたは自分自身でそれがどのように動作するかを理解することができます。

Answer 3

2番目と3番目の引数が最初の引数であるリスト内で同じように頻繁に発生する場合は、occurrences/5を書くことができます。第4引数と第5引数は対応するカウンタです。そして、述語個/ 1には、呼び出し元の述語です：

occurrences(List) :- 
    occurrences(List,a,b,0,0). 

occurrences([],_A,_B,N,N).  
occurrences([A|Xs],A,B,N0,M) :- 
    N1 is N0+1,     
    occurrences(Xs,A,B,N1,M).  
occurrences([B|Xs],A,B,N,M0) :- 
    M1 is M0+1, 
    occurrences(Xs,A,B,N,M1). 
occurrences([X|Xs],A,B,N,M) :- 
    dif(A,X), 
    dif(B,X), 
    occurrences(Xs,A,B,N,M). 

あなたは0でカウンターを開始し、対応するカウンタがインクリメントされるか、何のカウンターがあればインクリメントされていないAまたはBに等しいリストの先頭に応じて、頭は両方とも異なっている。今度は、あなたの挙げた例の結果を見てみましょう：

?- occurrences([a,a,b,b]). 
true ; 
false. 

?- occurrences([a,a,a,b,b]). 
false. 

は、しかし、私はあなたが2つの要素を指定することができます述語個/ 3がより有用であろうと思う：

occurrences(List,A,B) :- 
    dif(A,B),      
    occurrences(List,A,B,0,0).  

次にあなたの例ではなりを問い合わせます次のようになります。

?- occurrences([a,a,b,b],a,b). 
true ; 
false. 

?- occurrences([a,a,a,b,b],a,b). 
false. 

あなたはまた同じように頻繁に発生する要素を求めることができる：

?- occurrences([a,a,b,b,c,c,d],X,Y). 
X = a, 
Y = b ; 
X = a, 
Y = c ; 
X = b, 
Y = a ; 
X = c, 
Y = a ; 
X = b, 
Y = c ; 
X = c, 
Y = b ; 
dif(X, d), 
dif(X, c), 
dif(X, c), 
dif(X, b), 
dif(X, b), 
dif(X, a), 
dif(X, a), 
dif(X, Y), 
dif(Y, d), 
dif(Y, c), 
dif(Y, c), 
dif(Y, b), 
dif(Y, b), 
dif(Y, a), 
dif(Y, a). 

最後の解決策は、両方が等しく頻繁に出現する、すなわち0回であるので、リストに全く現れない2つの要素に対応する。述語を他の方向に使用する場合、つまり、2つの要素が同じように頻繁に表示されるようなリストがあるかどうかを調べるには、述語の時間にリストの長さを制限しているゴールに接頭辞を付ける必要があります例えば、呼び出し：

?- length(L,_),occurrences(L,a,b). 
L = [] ; 
L = [_G150], 
dif(_G150, b), 
dif(_G150, a) ; 
L = [a, b] ; 
L = [b, a] ; 
L = [_G116, _G119], 
dif(_G116, b), 
dif(_G116, a), 
dif(_G119, b), 
dif(_G119, a) ; 
L = [a, b, _G162], 
dif(_G162, b), 
dif(_G162, a) ; 
L = [a, _G159, b], 
dif(_G159, b), 
dif(_G159, a) ; 
L = [b, a, _G162], 
dif(_G162, b), 
dif(_G162, a) ; 
. 
. 
. 

Answer 4

ここで出現/ if_/3と5と=/3のよりコンパクトなバージョンです。このバージョンで

occurrences([],_A,_B,N,N). 
occurrences([H|T],A,B,N0,M0) :- 
    elem_x_count_(H,A,N1,N0), 
    elem_x_count_(H,B,M1,M0), 
    occurrences(T,A,B,N1,M1). 

elem_x_count_(E,X,New,Old) :- 
    if_(E=X, New is Old+1, New=Old). 

が対応をインクリメントするelem_x_count_/4を使用しています唯一の再帰的なルールがありますリストの先頭がAおよびに一致する場合はカウンタ引数そうでなければそれらをそのままにする。呼び出し述語は変更されません：すべての3つの引数が地面（開いたまま何もchoicepointsがないためtrue後;を押す必要はありません）している場合

occurrences(List,A,B) :- 
    dif(A,B), 
    occurrences(List,A,B,0,0). 

または

occurrences(List) :- 
    occurrences(List,a,b,0,0). 

この方法で述語が確定成功します。次の出現/ 3の古いバージョンのクエリ例を示します。

?- occurrences([a,a,b,b],a,b). 
true. 

もう1つの違いは、dif/2制約の数が少ないことです。例：

?- occurrences([a,a,b,b,c,c,d],X,Y). 
X = a, 
Y = b ; 
X = a, 
Y = c ; 
X = b, 
Y = a ; 
X = c, 
Y = a ; 
X = b, 
Y = c ; 
X = c, 
Y = b ; 
dif(X, d), 
dif(X, c), 
dif(X, b), 
dif(X, a), 
dif(X, Y), 
dif(Y, d), 
dif(Y, c), 
dif(Y, b), 
dif(Y, a). 

このクエリの最後の解決策のみが以前のバージョンと異なります。それは同じ結果を説明しますが、他のバージョンで2回出現したすべてのdifは一度しか現れません。他の例のクエリでも同じ回答が得られます。