0

リストが与えられたら、リスト内の可能なペアのすべての組み合わせを計算したいと思います。

例 2) 入力はリスト (a,b,c) (a,b) (a,c) (b,c) のペアを取得したい

例 1) 入力はリスト (a,b,c,d) (a,b) (a,c) (a,d) (b,c) (b,d) と (c) のペアを取得したい、d)

4

4 に答える 4

2

select/32 回 (またはselect/31 回と1 回)使用member/2すると、ここで目的を達成できます。詳細はお任せしますが、それでも難しい場合はご相談ください。

ところで、リストのProlog構文はそうではありません(a, b, c)（[a, b, c]まあ、それは構文糖ですが、それはそのままにしておきます）。

編集：@WillNessが指摘したように、ペアを探しているのではなく、リストの前にある(X, Y)ペアのみを探しています。XY

DCG は非常に適しています。@false が説明したように、グラフィカルに魅力的なソリューションを作成できます。

... --> [] | [_], ... .

pair(L, X-Y) :-
    phrase((..., [X], ..., [Y], ...), L).

別の方法として、SWI-Prolog を使用している場合は、 への呼び出しappend/2も同様の方法でトリックを行いますが、DCG よりも効率的ではありません。

pair2(L, X-Y) :-
    append([_, [X], _, [Y], _], L).

@WillNess がコメントで提案したように、基本的な再帰でそれを行うことができます。必要に応じて、この部分の詳細は彼に任せます。

于 2012-05-01T23:06:26.053 に答える
1

OK、Haskellの定義を翻訳するには

pairs (x:xs) = [ (x,y) | y <- xs ]
                ++ pairs xs 
pairs []     = []

（つまり、リスト内のヘッドxとテールのペアはxs、がのすべてのペア(x,y)でyあり、;xsのペアでもありxs、空のリストにはペアがありません）

バックトラックのProlog述語として、各REDOでペアを1つずつ生成するので、上記を1対1で簡単に書き直すことができます。

pair( [X|XS], X-Y) :- member( ... , XS)    % fill in 
                      ; pair( XS, ... ).   %    the blanks 
%% pair( [], _) :- false.

可能なすべてのペアを取得するには、次を使用しfindallます。

pairs( L, PS) :- findall( P, pair( L, P), PS).

bagofリストに論理変数を含めることができる場合は、使用を検討してください。bagofただし、バックトラックの制御は複雑な問題になる可能性があります。

pairs（ほぼ）決定論的、非バックトラッキング、再帰的定義として書くこともでき、関数型プログラミング言語が行うようにアキュムレータパラメータを介して出力リストを構築します-ここではトップダウン方式で、これはPrologが非常に優れていることです：

pairs( [X|T], PS) :- T = [_|_], pairs( X, T, T, PS, []). 
pairs( [_], []).
pairs( [], []).

pairs( _, [], [], Z, Z).
pairs( _, [], [X|T], PS, Z) :- pairs( X, T, T, PS, Z).
pairs( X, [Y|T], R, [X-Y|PS], Z) :- pairs( X, T, R, PS, Z).
于 2012-05-02T10:32:26.083 に答える
0

これを解決する可能な方法を次に示します。

次の述語combine/3は、3 番目の引数がペアを含むリストに対応し、各ペアの最初の要素が の最初の引数に等しい場合に真になりますcombine/3。各ペアの 2 番目の要素は、 predicate の 2 番目の引数のリストの項目に対応しますcombine/3。どのように動作するかの例combine/3:

?- combine(a,[b],X).
X = [pair(a,b)]

?- combine(a,[b,c,d],X).
X = [pair(a,b), pair(a,c), pair(a,d)]

可能な定義方法combine/3:

combine(A,[B],[pair(A,B)]) :- !.

combine(A,[B|T],C) :-
  combine(A,T,C2),          % Create pairs for remaining elements in T.
  append([pair(A,B)],C2,C). % Append current pair and remaining pairs C2.
                            % The result of append is C.

combine/3を定義するために使用できるようになりましたpair/2:

pairs([],[]).      % Empty list will correspond to empty list of pairs.
pairs([H|T],P) :-  % In case there is at least one element.
  nonvar([H|T]),   % In this case it expected that [H|T] is instantiated.
  pairs(H,T,P).

pairs(A,[B],[pair(A,B)]) % If remaining list contains exactly one element,
  :- !.                  % then there will be only one pair(A,B).
pairs(A,[B|T],P) :-      % In case there are at least two elements.
  combine(A,[B|T],P2),   % For each element in [B|T] compute pairs
                         % where first element of each pair will be A.
  pairs(B,T,P3),         % Compute all pairs without A recursively.
  append(P2,P3,P).       % Append results P2 and P3 together.

使用例:

?- pairs([a,b,c],X).
X = [pair(a, b), pair(a, c), pair(b, c)].

?- pairs([a,b,c,d],X).
X = [pair(a, b), pair(a, c), pair(a, d), pair(b, c), pair(b, d), pair(c, d)].
于 2019-05-24T18:35:46.023 に答える