Prolog list of transitive pairs

Question

I've been trying to solve the following problem for a while now, but can't seem to find the right solution.

Lets say there is a function test(X,Y,Z) such that X is a single pair of numbers, Y is a list of pairs, and Z is the resulting list of transitive pairs.

For example:

test((1,5), [(7,3),(5,2),(5,9)], Z).

Z = [(1,2),(1,9)]

(because of transitivity 1->5->2 and 1->5->9)

So far I've managed to create the following code:

test(_,[],_):- false.
test((X1,C),[(C,Y2)|_],(X1,Y2)).
test((X1,X2),[_|YT],Result) :- test((X1,X2),YT,Result).

It returns each individual result pair like so:

Z = (1, 2) ;
Z = (1, 9) ;

But I can't seem to return them all into a single list like in the example above:

Z = [(1,2),(1,9)]

Any help would be greatly appreciated.

Shon Shon · Accepted Answer · 2013-10-28T21:16:29

I think the problem is that you're not building the list of transitive pairs. You're just returning a single pair as the third argument of test/3.

Here's one possible solution:

I made a predicate to handle comparing pairs and describing their transitive marriage, so that i didn't have to juggle those tuples in the subsequent rules:

transit((X,T), (T,Y), (X,Y)).

Then it's just a matter of standard list processing with recursive predicates:

t(_, [], []).
t(X, [T|ToTransit], [Y|Transited]) :-
    transit(X,T,Y),
    t(X,ToTransit,Transited).
t(X, [T|ToTransit], Transited) :-
    \+ transit(X,T,_),
    t(X,ToTransit, Transited).

Of course, once you have a predicate like transit/3 that defines the relation, you can also do something like

findall( TP,
         ( member(T, [(2,2), (2,5), (1,5)]), transit((1,2), T, TP) ),
         Tps).

Prolog list of transitive pairs

1 Answers