0

Prologでユニオン関数を書き込もうとしていますが、問題が発生しています。私は例を調べて、ユニオンの組み込みの例をリストしましたが、私は課題のために自分で書いています。リストの値が重複している場合や、リストの順序が昇順でない場合に、奇妙な結果が生じることに気づきました。組み込みのユニオンコードは次のとおりです。

union([], A, A) :- !.
union([A|C], B, D) :-
        memberchk(A, B), !,
        union(C, B, D).
union([A|B], C, [A|D]) :-
        union(B, C, D).

ここでの擬似コードは、結果内でリスト1のすべてを検索し、それが使い果たされたら、リスト2とリスト3を比較することだと思います。これらは同じである必要があります。ただし、これは順序をチェックしません。

30 ?- union([1,2,3],[],[3,2,1]).
false.

なぜこれは間違っているのですか？リスト1とリスト3は、順序は異なりますが同じセットです。

24 ?- union([a],[a,a],[a,a]).
true.

25 ?- union([a,a],[a],[a,a]).
false.

これら2つの違いは何ですか？それらは同じ結果をもたらすはずです。ただし、関数の記述方法により、最終的には、25行目で異なるリスト2とリスト3を比較するだけです。

私の質問はです。。。重複が適切に処理され、順序が重要にならないように、これらの関数を作成するためのより良い方法はありますか？組み込みのメソッドはトリックを実行しますが、サイコロは実行しないと想定されます。

4

3 に答える 3

1

まず、一貫した名前で記述されたコードは読みやすくなります。

union([], A, A) :- !.
union([A|B], C, D) :-
        memberchk(A, B), !,
        union(B, C, D).
union([A|B], C, [A|D]) :-
        union(B, C, D).

それは何をするためのものか？A2 つのリストとが与えられると、 に存在しないBすべての要素の接頭辞が付いた結果が生成され、次にそれ自体が生成されます。だから、。そしてまた。ここで順序が保持されていることがわかります。したがって、順序に関係なくリストを比較したい場合は、そのための特別な追加の述語を作成する必要があります。ABBunion([1,2,3],[],[1,2,3])union([1,2,3],[2],[1,3,2])union([1,2,3],[],X), regardless(X,[3,2,1])

重複と同じ - セット等価述語は無視する必要があります。union上記のように、OTOH はセットではなく、リストに関するものです。同じセットを表すさまざまなリストがありますが、リストとしては異なるものと見なされます。

あなた25は重複の問題にぶつかりました:union([a,a],[a],X)生成しX=[a]ます。繰り返しますが、セットとしては と同じです[a,a]が、リストとしては異なります。

これに対処するための1つの戦略は、セットを厳密に増加するリストとして表現することです-要素の順序が明確に定義されている場合。次に、その定義に従って2つのセットunionが与えられると、それもセットを生成し、それで効率的に機能するように書くことができます:

union([],X,X):-!.
union(X,[],X):-!.
union([A|B],[C|D],[H|T]):-
  A @< C -> H=A, union(B,[C|D],T) ;
  C @< A -> H=C, union([A|B],D,T) ;
  H=A, union(B,D,T).

make_set/2ここでも述語を定義する必要があります。(いくつかの点で) さらに優れているのは、自己均衡バイナリ ツリーによってセット (ここでも比較可能な要素の) を表すことです。

于 2013-01-28T10:57:54.873 に答える
0

union(?A, ?B, ?C)(つまり、任意の変数を入力または出力として使用できる) を作成するには、新しい共用体を作成します。

uniao(?A, ?B, ?C)

list:union次のように、とりわけ使用します。

uniao([], [], []) :- !.

uniao(X, [], X) :- !.

uniao([], X, X) :- !.

uniao(X, Y, Z) :-
    nonvar(X),
    nonvar(Y),
    var(Z),
    list_to_set(X, Xs),
    list_to_set(Y, Ys),
    union(Xs, Ys, Z), 
    !.  

uniao(X, Y, Z) :-
    nonvar(X),
    var(Y),
    nonvar(Z),
    list_to_set(X, Xs),
    list_to_set(Z, Zs),
    subset(Xs, Zs),
    subtract(Zs, Xs, Y), 
    !.  

uniao(X, Y, Z) :-
    var(X),
    nonvar(Y),
    nonvar(Z),
    list_to_set(Y, Ys),
    list_to_set(Z, Zs),
    subset(Ys, Zs),
    subtract(Zs, Ys, X),
    !.

uniao(X, Y, Z) :-
    nonvar(X),
    nonvar(Y),
    nonvar(Z),
    list_to_set(X, Xs),
    list_to_set(Y, Ys),
    list_to_set(Z, Zs),
    union(Xs, Ys, Ts),
    subtract(Zs, Ts, []),
    subtract(Ts, Zs, []),
    !.
于 2015-12-15T16:04:29.997 に答える
0

you are implementing a concept using the 'tools' that the language (Prolog, in your case) put in your hands. Then you should better define (in natural language, first) what's your target, considering that also append/3 could fit the union concept.

you can call list C a union among lists A,B if....

I would fill the ellipsis this way

  • each A element appears once in C and
  • each B element appears once in C and
  • each C element appears in A or B

If you agree on this definition, then an implementation could be

union(A, B, C) :-
  elems_once(A, [], C1),
  elems_once(A, C1, C2),
  each_elems(C2, A, B, C).

That is far less efficient that the library code shown, but it's the price of generality...

于 2013-01-28T11:02:05.527 に答える