任意の順序で2つのリストの平等を見つけるためのプロログプログラム

StackOverflow https://stackoverflow.com/questions/2710479

質問

2つのリストの平等を見つけるためにPrologプログラムを書きたかったのですが、ここでは要素の順序があります
関係ない。だから私は次のことを書きました：

del(_, [], []) .
del(X, [X|T], T).  
del(X, [H|T], [H|T1]) :-
   X \= H,
   del(X, T, T1).

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

equal([], []).  
equal([X], [X]).  
equal([H1|T], L2) :-
   member(H1, L2),
   del(H1, L2, L3),
   equal(T, L3).

しかし、私がのような入力を与えるとき equal([1,2,3],X)., 、すべての可能な値を示しているわけではありません X. 。代わりに、プログラムは中央にぶら下がっています。理由は何でしょうか？

役に立ちましたか？

解決 

isSubset([],_).
isSubset([H|T],Y):-
    member(H,Y),
    select(H,Y,Z),
    isSubset(T,Z).
equal(X,Y):-
    isSubset(X,Y),
    isSubset(Y,X).

他のヒント

1つのセットが他のセットの順列であるかどうかをチェックする述語を使用してみてください。

delete(X, [X|T], T).

delete(X, [H|T], [H|S]):-
    delete(X, T, S).


permutation([], []).

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

（から取られた述語 http://www.dreamincode.net/code/snippet3411.htm)

?- permutation([1,2,3],[3,1,2]).
true

あなたが観察した非終了の実際の理由はこれです：次の条項は制約しません L2 何らかの形で、形、または形。

等しい（[h1 | t]、l2）： - メンバー（h1、l2）,
   del(H1, L2, L3),
   equal(T, L3).

だからあなたのクエリ ?- equal([1,2,3], X). 目標を証明することを意味します member(_, L2) 普遍的に終了しません。したがって equal([1,2,3], X) 普遍的に終了することもできません！

Prologコードの不均衡を説明する方法の詳細については、について読んでください !

詩別の角度から終了の問題を見ると、非終了は実際には、 必要な結果 この場合。

なんで？なぜなら、あなたは多様性の数を制限しないため、ソリューションのサイズが無限に設定されるからです。このセットは、有限数の回答で表すことはできません（目標の遅延を許可しない場合）。

リスト要素の多重性を気にしない場合は、十分なインスタンスを確認してくださいground/1, 、それを強制しますiwhen/2, 、および重複を排除します sort/2 そのようです：

same_elements(As, Bs) :-
   iwhen(ground(As+Bs), (sort(As,Es),sort(Bs,Es))).

SWI Prolog 8.0.0でのサンプルの使用：

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

?- same_elements([a,b,b,a], [b,a,b,e]).
false.

?- same_elements([a,b,b,a], Xs).
エラー：引数は十分にインスタンス化されていません

これを試して：

equal([],[]).
equal([Ha|Ta],[Hb|Tb]) :-
   Ha = Hb, lequal(Ta,Tb).

どうですか：

equal(X, Y) :-
    subtract(X, Y, []),
    subtract(Y, X, []).

なぜそうするのですか equal([1,2,3], X) あなたのコードで普遍的に終了しませんか？

を見てみましょう あなたのコードの！障害スライスとは何ですか？これがタグ情報です：

故障スライスは、いくつかの目標を追加することによって得られたプロログプログラムの断片です false. 。故障スライスは、純粋な単調プロログプログラムの普遍的な不均衡の理由をローカライズするのに役立ちます。また、必要な推論の数の下限を与えるのにも役立ちます。コンクリートです 技術。

障害スライスを作成するには：

  • 挿入します 偽 プログラムの目標
  • フラグメントが上記の目標で終了しないことを確認しながら。
del（_、[]、[]）： - 偽.
del（x、[x | t]、t）： - 偽.
del（x、[h | t]、[h | t1]）： - 偽,
   dif（x、h）,                    % note that the OP originally used `X \= H`
   del（x、t、t1）.

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

同等（[]、 []） ：- 偽.
等しい（[x]、[x]）： - 偽.
equal([H1|T], L2) :-
   member(H1, L2), 偽,
   del（H1、L2、L3）,
   等しい（T、L3）.  

?- equal([1,2,3], _), 偽.     % note that `false` is redundant ...
**ループ**                      % ... as above `equal/2` cannot succeed.

だから...上記の故障スライスは私たちに何を教えてくれますか？それは言う：

  • 目標を達成するために equal([1,2,3], X) 普遍的に終了します...
  • ... 私たち 変更する必要があります 少なくとも1つ 残りの部品 （そうではありません ストリキングされたスルー)!

組み込みの述語を使用することをお勧めします msort/2, 、リストを比較します。 SWI PrologではO（nlogn）時間がかかりますが、未解決のリストをチェックするには、要素ごとにo（n（n）がかかります。2） 時間。

lists_equal(List1, List2) :-
    msort(List1, Sorted1),
    msort(List2, Sorted2),
    Sorted1=Sorted2.

ここでは、並べ替えリストにはO（nlogn）時間がかかり、それらを比較するにはswi prologでo（n）時間がかかりますが、他の実装については知りません。

簡単に

equal([],[]).
equal([H|T],[H|T1]):-equal(T,T1).
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top