6

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

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

これは、まったく同じ順序の入力に対して完全に機能します。例えば：

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

ただし、次のような入力には使用できません。

?- 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).

これはサブセットではうまく機能しますが、適切なサブセットでは機能しません。私の問題は、proper/4 の 2 番目の節がどのように機能するかを理解していることから生じていると思います。どんな助けでも大歓迎です。

編集：

最初のリストが 2 番目の適切なサブセットであり、2 番目のリストが最初の適切なサブセットであるかどうかを判断しようとしていたことに気付きました。より正確になるようにコードをクリーンアップしました。

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

1 に答える 1

2

私が正しく理解している場合、最後の試みの最初の 2 つの宣言は、1 つの要素を持つリストが空のリスト (false) の適切なサブセットであり、空のリストが 1 つの要素を持つリストの適切なサブセットであることを意味します。 （真実）; と同様に成功するため、最初のものは問題になるはずですが、適切なサブセット関係は非対称です。proper([1], [])proper([],[1])

2回目の試行で同一のサブセットが除外されない理由は、AがBよりも小さいことを要求する宣言がないためだと思います.

ここに私が思いついたいくつかの可能な解決策があります。smaller_set/2明快さと簡潔さを増すために、私は数回使用します。

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

def_proper_subset/2サブセットの標準定義をキャプチャしようとします。

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 の一致する各要素を削除することに基づく、再帰的な定義の例。A が B の前に要素を使い果たした場合にのみ成功することで、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).

これは、補助述語を使用して、主述語が 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ただし、これらの種類のソリューションは、サブリストを見つけるためにも機能します。
  • def_proper_subset/2AがBのサブセットであることを確認するだけで機能し、AでBのサブセットを生成できないため、これは一種のくだらない解決策だと思います。他の2つは考えることができます。

(失敗して のグラウンド定義を含めるのを忘れていましたが、rec_proper_subset2/2修正しました)。

于 2013-10-24T21:11:32.503 に答える