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/3两次（或select/3一次member/2又一次）将使您在这里实现您想要的。我会让你弄清楚细节，如果仍然麻烦，我会寻求帮助。

顺便说一句，列表的 Prolog 语法不是(a, b, c)但是[a, b, c]（好吧，它是语法糖，但我会留在那里）。

编辑：正如@WillNess 指出的那样，您不是在寻找任何对(X, Y)，而只是在寻找列表X中之前Y的对。

DCG 非常适合：正如@false 所描述的，它们可以产生一个图形吸引人的解决方案：

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

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

或者，如果您使用 SWI-Prolog，也可以调用 toappend/2以类似的方式来解决问题，但效率低于 DCG：

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

正如@WillNess 在他的评论中所建议的那样，您可以通过基本递归来做到这一点。如果需要，我将把这部分留给他详细说明！

于 2012-05-01T23:06:26.053 回答
1

好的，所以翻译 Haskell 定义

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

（这意味着，列表中带有 headx和 tail的对是 inxs的所有对(x,y)，y也是 inxs的对xs；并且在空列表中没有对）

作为回溯Prolog 谓词，在每次重做时一一生成对，这是对上述内容的直接一对一重写，

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

您可以使用append/来遍历列表：

?- append(_,[X|R],[a,b,c,d]).
X = a,
R = [b, c, d] ;
X = b,
R = [c, d] ;
X = c,
R = [d] ;
X = d,
R = [] ;
false.

接下来，用于member/2形成一对X-Y，对于每个Yin R：

?- append(_,[X|R],[a,b,c,d]), member(Y,R), Pair=(X-Y).
X = a,
R = [b, c, d],
Y = b,
Pair = a-b ;
X = a,
R = [b, c, d],
Y = c,
Pair = a-c ;
X = a,
R = [b, c, d],
Y = d,
Pair = a-d ;
X = b,
R = [c, d],
Y = c,
Pair = b-c ;
X = b,
R = [c, d],
Y = d,
Pair = b-d ;
X = c,
R = [d],
Y = d,
Pair = c-d ;
false.

然后，用于findall/3收集列表中的所有对：

?- findall(X-Y, (append(_,[X|R],[a,b,c,d]), member(Y,R)), Pairs).
Pairs = [a-b, a-c, a-d, b-c, b-d, c-d].

因此，您的最终解决方案可以表示为：

pairs(List, Pairs) :-
    findall(X-Y, (append(_,[X|R],List), member(Y,R)), Pairs).

一个使用示例是：

?- pairs([a,b,c,d], Pairs).
Pairs = [a-b, a-c, a-d, b-c, b-d, c-d].
于 2019-05-25T16:01:50.960 回答
0

这是解决此问题的一种可能方法。

如果第三个参数对应于包含对的列表，则以下谓词combine/3为真，其中每对的第一个元素等于 的第一个参数combine/3。每对的第二个元素将对应于 predicate 的第二个参数中的列表项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 回答