How to predicate all pairs in a given list in Prolog?

Question

When given a list I would like to compute all the possible combinations of pairs in the list.

e.g 2) input is a list (a,b,c) I would like to obtain pairs (a,b) (a,c) (b,c)

e.g 1) input is a list (a,b,c,d) I would like to obtain pairs (a,b) (a,c) (a,d) (b,c) (b,d) and (c,d)

Answer 1

Using select/3 twice (or select/3 once and member/2 once) will allow you to achieve what you want here. I'll let you work out the details and ask for help if it's still troublesome.

BTW, Prolog syntax for list isn't (a, b, c) but [a, b, c] (well, it's syntactic sugar but I'll leave it at that).

edit: as @WillNess pointed out, you're not looking for any pair (X, Y) but only for pairs where X is before Y in the list.

DCGs are a really good fit: as @false described, they can produce a graphically appealing solution:

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

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

Alternatively, if you use SWI-Prolog, a call to append/2 does the trick too, in a similar manner, but is less efficient than DCGs:

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

You can do it with a basic recursion, as @WillNess suggested in his comment. I'll leave this part for him to detail if needed!

Answer 2

OK, so to translate the Haskell definition

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

(which means, pairs in the list with head x and tail xs are all the pairs (x,y) where y is in xs, and also the pairs in xs; and there's no pairs in an empty list)

as a backtracking Prolog predicate, producing the pairs one by one on each redo, it's a straightforward one-to-one re-write of the above,

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

To get all the possible pairs, use findall:

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

Consider using bagof if your lists can contain logical variables in them. Controlling bagof's backtracking could be an intricate issue though.

pairs can also be written as a (nearly) deterministic, non-backtracking, recursive definition, constructing its output list through an accumulator parameter as a functional programming language would do -- here in the top-down manner, which is what Prolog so excels in:

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

Answer 3

Here is a possible way of solving this.

The following predicate combine/3 is true if the third argument corresponds to a list contains pairs, where the first element of each pair is equal to the first argument of combine/3. The second element of each pair will correspond to an item of the list in the second argument of the predicate combine/3. Some examples how combine/3 should work:

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

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

Possible way of defining 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.

Now combine/3 can be used to define 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.

Sample usage:

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

Answer 4

You can use append/ to iterate through the list:

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

Next, use member/2 to form a pair X-Y, for each Y in 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.

Then, use findall/3 to collect all pairs in a list:

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

Thus, your final solution can be expressed as:

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

An example of use is:

?- pairs([a,b,c,d], Pairs).
Pairs = [a-b, a-c, a-d, b-c, b-d, c-d].