適切なサブセット - プロローグ

Question

入力として2つのリストを取り、適切なサブセットをチェックするプログラムを作成しようとしています。私はで始まった：

proper([A],[]). 
proper([],[A]). 
proper([A|T1],[A|T2]) :- proper(T1,T2). 

これは完全に同じ順序で入力に対して完璧に機能します。例えば：

?- proper([a,b,c],[a,b,c,d]). 
Yes 

しかしなどの入力のためにされていません。私を導く

Subset function in prolog

を：

?- proper([a,b,c],[b,d,a,c]). 
No 

サイトを見た後、私は、これは以前の質問をしました私のコードをそのように変更する：

proper([A],[]). 
proper([],[A]). 
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2). 
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2). 

これはサブセットでは問題ありませんが、適切なサブセットでは問題ありません。私の問題は、正しい/ 4の第2節がどのように働くかを私が理解することから生ずると思います。すべての助けが大歓迎です。

編集：

私は最初のリストは、第二と第二の適切なサブセットは、最初の適切なサブセットあったかどうかを判断しようとしていた実現。より正確になるようにコードをクリーンアップしました。

proper([],_). 
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2). 
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2). 

Answer 1

私が正しく理解していれば、あなたの最後の試みで、最初の2つの宣言は、1つの要素と両方リストが空リスト（偽）の適切なサブセットである、ことを意味し、と空のことlistは、1つの要素を持つリストの適切なサブセットです（true）。 proper([1], [])がproper([],[1])だけでなく、成功するために最初のものは、問題となるはずですが、適切なサブセット関係は非対称です。私はあなたの第二の試みが同一のサブセットを除外していない理由は、あなたがここB.

よりも小さくする必要が何の宣言を持っていないことであると考えてい

は私が思いついたいくつかの可能なソリューションです。私はsmaller_set/2を数回使用して明瞭さと簡潔さを向上させました。

smaller_set(A, B) :- 
    length(A, LA), 
    length(B, LB), 
    LA < LB. 

def_proper_subset/2サブセットの標準定義を取得しようとします。 AはB.

rec_proper_subset1([], [_|_]). 
rec_proper_subset1([_e|A], B) :- 
    select(_e, B, C),   % C is B with _e removed. Only true if _e is in B. 
    rec_proper_subset1(A, C). 

この前の要素がなくなった場合にそれが唯一の後続によって< Bことを確実にAとBの各整合素子をremoveingに基づい

再帰的定義に

def_proper_subset(A, B) :- 
    smaller_set(A, B),     % if A < B then there's some _e in B that isn't in A. 
    forall(member(_e, A), member(_e, B)). 

例えば、主述語が既にA < Bを保証している場合には、補助語述語を使用してメンバーシップをチェックする。

rec_proper_subset2(A, B) :- 
    smaller_set(A, B), 
    rec_proper_subset2_(A, B). 

rec_proper_subset2_([], _). 
rec_proper_subset2_([_e|A], B) :- 
    member(_e, B), 
    rec_proper_subset2_(A, B). 

編集：

• あなたはあなたのリストが重複する要素を持っていないことを確認したい場合はlist_to_set/2、sort/2、または類似のものを使用する必要があります。しかし、これらの種類のソリューションは、サブリストの検索にも役立ちます。
• 私はがAがBのサブセットだがAのサブセットは生成できないことを確認するためにしか役に立たないので、ちょっとした解決策だと思う。他の2つは考えられる。

（rec_proper_subset2/2の地面の定義を含むのを忘れてしまったが、これを修正した）