3

私は Prolog を初めて使用し、2 つのリストにまったく同じ要素があるかどうかを確認するのに問題があります。要素が異なる順序である可能性があります。私はこのコードを持っています:

myremove(X, [X|T], T).   
myremove(X, [H|T], [H|R]) :-
   myremove(X, T, R).

 same_elements([], []).
 same_elements([H1|T1], L2) :-      
    myremove(H1, L2, Nl2),  
    same_elements(T1, Nl2).

それを除いて動作します

?- same_elements([b,c,a], X).

最初の結果を返した後、メモリ不足エラーが発生します。そこで、リストの長さが等しいことを確認し、H1 が L2 のメンバーであることを確認して、結果セットを絞り込もうとしました。

mylength([], 0).
mylength([_|T], R) :-
   mylength(T, Nr),
   R is Nr+1.

mymember(X, [X|_]).
mymember(X, [_|T]) :-
   mymember(X, T).

same_elements([], []).
same_elements([H1|T1], L2) :- 
   mylength([H1|T1], X),
   mylength(L2, Y),
   Y = X,
   mymember(H1, L2),
   myremove(H1, L2, Nl2),
   same_elements(T1, Nl2).

今は両方

?- same_elements([b,c,a], X).
?- same_elements(X, [b,c,a]). 

すべての結果を返しますが、最後にハングします。これを行うより良い方法はありますか?

4

2 に答える 2

7

簡単な答え: はい。

しかし、これに入る前に、もっと興味深い質問があります: どのようにしてそれらの問題を見つけましたか? あなたはそれらを見つけることができて本当に幸運だったに違いありません!私は試した:

?- same_elements([a,b,c,d,e,f,g],Xs).
Xs = [a、b、c、d、e、f、g];
Xs = [a、b、c、d、e、g、f] ;
Xs = [a、b、c、d、f、e、g] ;
Xs = [a、b、c、d、g、e、f] ;
...

...そして、作成されたソリューションに圧倒されるだけでした。いいえ、すべての回答を確認する忍耐力がありませんでした。しかし、具体的なクエリをテストする簡単な方法があります。単純に回答を削除し、クエリが停止するかどうかだけに集中します。この目的のために、次の目標を追加しfalseます。

?- same_elements([a,b,c,d,e,f,g],Xs), false .

今、私たちは決して解決策を見ることはありません。しかし、クエリの終了が観察される場合があります。残念ながら、このクエリはおそらくループします。少なくとも、関係のない解決策に悩まされることはなくなりました。

終了しない理由をさらに絞り込むためfalseに、プログラムに目標を追加します。その変更されたプログラムは、障害スライスと呼ばれます。このようにして、不始末の原因となっている部分を絞り込んでいきます。falseプログラムがまだ終了しないように目標を追加することに成功した場合、問題を修正する方法について優れた手がかりが得られます。例えば:

same_elements([], [])。
same_elements([H1|T1], L2) :-
  mylength([H1|T1], X), false, 
  mylength(L2, Y), 
  Y = X, 
  mymember(H1, L2), 
  myremove(H1, L2, Nl2), 
  same_elements(T1, Nl2).

したがって、これは目標があることを除いて、ほとんどあなたのプログラムfalseです。背後にある目標falseは、それらが無関係であることを明確にするために取り消し線が引かれています。

これで、クエリは終了します。

?- same_elements([a,b,c,d,e,f,g],Xs), false .
間違い。

そのため、すでに削除しすぎています。次の試行:

same_elements([], [])。
same_elements([H1|T1], L2) :-
  mylength([H1|T1], X),
  mylength(L2, Y), false, 
  Y = X, 
  mymember(H1, L2), 
  myremove(H1, L2, Nl2), 
  same_elements(T1, Nl2).

今、クエリは終了しません!

つまり、プログラムの残りの部分を見ないでください。そこに書かれていることは何でも、このループを元に戻すことはできません!

これで、目に見える部分について考えることができます。

?- same_elements([a,b,c,d,e,f,g],Xs).

のためでもない

?- same_elements(Xs,[a,b,c,d,e,f,g]).

そして犯人は、プログラムのこの非常に小さな部分です。

あなたのアイデアは、両方のリストが同じ長さであることを確認することでした。

length-predicate を使用する代わりに、新しいものを定義します。

list_same_length([], [])。
list_same_length([_|Xs], [_|Ys]) :-
    list_same_length(Xs, Ys)。

これは「両方向」で終了します。

于 2012-10-28T19:15:46.640 に答える