8


要素の順序が問題にならない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。代わりに、プログラムが途中でハングします。その理由は何ですか?

4

9 に答える 9

8
isSubset([],_).
isSubset([H|T],Y):-
    member(H,Y),
    select(H,Y,Z),
    isSubset(T,Z).
equal(X,Y):-
    isSubset(X,Y),
    isSubset(Y,X).
于 2010-04-27T21:05:02.717 に答える
4

セットの 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 
于 2011-11-21T18:52:08.510 に答える
1

これを試して:

equal([],[]).
equal([Ha|Ta],[Hb|Tb]) :-
   Ha = Hb, lequal(Ta,Tb).
于 2010-06-03T21:40:50.823 に答える
0

組み込みの predicate を使用してmsort/2から、リストを比較することをお勧めします。SWI Prolog では O(nlogn) 時間かかりますが、ソートされていないリストを単純に要素ごとにチェックすると O(n 2 ) 時間かかります。

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

ここでは、リストの並べ替えに O(nlogn) の時間がかかり、SWI Prolog ではそれらの比較に O(n) の時間がかかります。他の実装についてはわかりません。

于 2014-03-29T19:02:41.583 に答える
-1

簡単に

equal([],[]).
equal([H|T],[H|T1]):-equal(T,T1).
于 2014-04-12T05:11:55.057 に答える