6

ISO Prolog で、線形時間で実行される変数の 2 つのリストの共通部分の (メタ論理) 述語を定義する方法は? 変数は、決まった順序で表示されます。変数の「年齢」のような実装依存のプロパティは、結果に影響を与えてはなりません。

に類推してlibrary(ordsets)、関係を呼び出しましょうvarset_intersection(As, Bs, As_cap_Bs).

?- varset_intersection([A,B], [C,D], []).
true.

?-varset_intersection([A,B], [B,A], []).
false.

?- varset_intersection([A,B,C], [C,A,D], Inter).
Inter = [A,C].
or
Inter = [C,A].

?- varset_intersection([A,B],[A,B],[A,C]).
B = C
or
A = B, A = C

?- varset_intersection([A,B,C],[A,B],[A,C]).
idem

つまり、3 番目の引数は出力引数であり、最初の 2 つの引数の共通部分と一致します。

現在の ISO 標準 (Cor.2 を含む ISO/IEC 13211-1:1995 )のビルトインのリストを参照してください。

(注意してください、私は数年前に別の質問の過程でこの質問に答えました。しかし、それは非表示のままであり、Google には表示されません。)

4

4 に答える 4

3

term_variables/2最初の引数のサイズに線形の時間で機能する場合、これは機能する可能性があります。

varset_intersection(As, Bs, As_cap_Bs):-
    term_variables([As, Bs], As_and_Bs),
    term_variables(As, SetAs),
    append(SetAs, OnlyBs, As_and_Bs),
    term_variables([OnlyBs, Bs], SetBs),
    append(OnlyBs, As_cap_Bs, SetBs).

各共通変数は、指定された 2 つのリストに何回表示されても、結果リストに 1 回だけ表示されます。

?- varset_intersection2([A,_C,A,A,A], [A,_B,A,A,A], L).
L = [A].

また、次の場合のように奇妙な結果になる可能性があります。

?- varset_intersection([A,_X,B,C], [B,C,_Y,A], [C, A, B]).
A = B, B = C.

（permutation/2ここで役立つかもしれません）。

于 2015-01-04T16:05:16.797 に答える
2

copy_term/2線形時間を使用する場合、次のように機能すると思います。

varset_intersection(As, Bs, Cs) :-
    copy_term(As-Bs, CopyAs-CopyBs),
    ground_list(CopyAs),
    select_grounded(CopyBs, Bs, Cs).

ground_list([]).
ground_list([a|Xs]) :-
    ground_list(Xs).

select_grounded([], [], []).
select_grounded([X|Xs], [_|Bs], Cs) :-
    var(X),
    !,
    select_grounded(Xs, Bs, Cs).
select_grounded([_|Xs], [B|Bs], [B|Cs]) :-
    select_grounded(Xs, Bs, Cs).

アイデアは、1 回の呼び出しで両方のリストをコピーしてcopy_term/2、それらの間の共有変数を保持し、最初のコピーの変数を固定してから、2 番目のコピーの固定された位置に対応する 2 番目のリストの元の変数を選択することです。

于 2015-04-03T13:31:54.603 に答える
1

定数時間で失敗または成功した場合unify_with_occurs_check(Var, ListOfVars)、この実装は線形時間で回答を生成する必要があります。

filter_vars([], _, Acc, Acc).
filter_vars([A|As], Bs, Acc, As_cap_Bs):-
    (
        \+ unify_with_occurs_check(A, Bs)
      ->
        filter_vars(As, Bs, [A|Acc], As_cap_Bs)
      ;
        filter_vars(As, Bs, Acc, As_cap_Bs)
    ).

varset_intersection(As, Bs, As_cap_Bs):-
    filter_vars(As, Bs, [], Inter),
    permutation(Inter, As_cap_Bs).

指定されたリストに重複が含まれている場合、この実装には問題があります。

?- varset_intersection1([A,A,A,A,B], [B,A], L).
L = [B, A, A, A, A] ;

?- varset_intersection1([B,A], [A,A,A,A,B], L).
L = [A, B] ;

編集済み:bagof/3以下のコメントの @false による観察のおかげで、手動で作成されたフィルターに変更されました。

于 2015-01-04T11:13:51.850 に答える
0

考えられる解決策は、ブルーム フィルターを使用することです。衝突の場合、結果が間違っている可能性がありますが、より衝突耐性の高い関数が存在します。以下は、単一のハッシュ関数を使用する実装です。

sum_codes([], _, Sum, Sum).
sum_codes([Head|Tail], K, Acc,Sum):-
    Acc1 is Head * (256 ** K) + Acc,
    K1 is (K + 1) mod 4,
    sum_codes(Tail, K1, Acc1, Sum).

hash_func(Var, HashValue):-
    with_output_to(atom(A), write(Var)),
    atom_codes(A, Codes),
    sum_codes(Codes, 0, 0, Sum),
    HashValue is Sum mod 1024.

add_to_bitarray(Var, BAIn, BAOut):-
    hash_func(Var, HashValue),
    BAOut is BAIn \/ (1 << HashValue).

bitarray_contains(BA, Var):-
    hash_func(Var, HashValue),
    R is BA /\ (1 << HashValue),
    R > 0.

varset_intersection(As, Bs, As_cap_Bs):-
    foldl(add_to_bitarray, As, 0, BA),
    include(bitarray_contains(BA), Bs, As_cap_Bs).

foldl/4とが ISO ではないことは知っていinclude/3ますが、その実装は簡単です。

于 2015-01-04T12:49:22.047 に答える