I need to create a Cartesian product calculator for Prolog. It should work like this:
Input: product([1,2,3], [a,b], X).
Output: X = [[1,a],[2,a],[3,a],[1,b],[2,b],[3,b]].
I know there are examples on the Internet, but I wanted to write something myself.
This is my code and I think it's pretty close, but for some reason it doesn't exactly work. Any ideas, guys?
% call new with 4 parameters (so we can keep List1 in memory)
product(L1,L2,L3):- product(L1,L2,L3,L1).
% stop when both List1 and List2 are empty
product([], [], [], []).
% first list is empty, recreate it and work it again with the next element of second list (and shorten memory)
product([], [_|T2], List3, [H4|T4]):-
product([H4|T4], T2, List3, T4).
%go through first list and always first element of second list to our answer
product([H1|T1], [H2|T2], [[H1,H2]|T3], List4):-
product(T1, [H2|T2], T3, List4).
As said by Coder (+1), you should change the terminal clause from
product([], [], [], []).
to
product(_, [], [], _).
But ins't enough.
You shuold change che third clause from
product([], [_|T2], List3, [H4|T4]):-
product([H4|T4], T2, List3, T4).
to
product([], [_|T2], List3, L4):-
product(L4, T2, List3, L4).
I mean: is an error to consume the saved list 1.
With your version, from
product([1,2,3,4,5], [a,b,c,d], X),
you get only
[[1,a],[2,a],[3,a],[4,a],[5,a],[1,b],[2,b],[3,b],[4,b],[5,b],[2,c],[3,c],[4,c],[5,c],[3,d],[4,d],[5,d]]
That is: you loose [1,c], [1,d] and [2,d].
You should change the clause:
product([], [], [], []).
to:
product(_, [], [], _).
That's because when L2 gets empty it calls product(L1,[],L3,L4) where L1 and L4 are not empty. Your base case must be when L2 gets empty (then L3 gets empty as output list) and other lists may have elements:
?- product([1,2,3], [a,b], X).
X = [[1, a], [2, a], [3, a], [1, b], [2, b], [3, b]] ;
false.
In SWI-Prolog, it is also possible to generate the Cartesian product using the findall/3 and member/2 predicates:
:- initialization(main).
:- use_module(library(chr)).
main :-
product([1,2,3], [a,b], X),
writeln(X).
product(A,B,C) :-
findall([X,Y],(member(X,A),member(Y,B)),C).
This program prints [[1,a],[1,b],[2,a],[2,b],[3,a],[3,b]].
