CODEWITHSUNDEEP
recursionprolog
Roumen Roussev
Roumen Roussev

Reputation: 1

Prolog – How to recursively generate all combinations of two lists as a two-dimensional array

I tried to generate all the combinations of the elements in two lists. For example, List([1,2,3],[1,2,3],L). should return L = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]] This is the code I wrote:

matrix(L1, L2, M, Res).
matrix([], L2, [], []).
matrix([H1|T1], L2, M, [M|Res]):- matrix(T1, L2, M_temp, Res), combo(L2, H1, [], M).
combo ([], _, Acc, Acc) :- !.
combo ([H2|T2], H_tmp, Acc, M) :- combo (T2, H_tmp, Acc, M_tmp), M = [[H_tmp,H2]|M_tmp].

but the result is: L = [[[1,1],[1,2],[1,3]],[[2,1],[2,2],[2,3]],[[3,1],[3,2],[3,3]]] because I add the list as element instead of append each list element to Res. No success of implementing the the append.

append([1,2,3],[1,2,3],L).
append_lst([], L2, L2).
append_lst([H|T], L2, Res) :- append_lst(T, L2, Acc), Res = [H|Acc].

I think my approach is wrong. Could you help me, please?

Upvotes: 0

Views: 177

Answers (1)

Nicholas Carey
Nicholas Carey

Reputation: 74307

Well, Prolog doesn't have arrays: it just has lists. But, assuming your have two lists/sets, say

  • [1,2,3]
  • [a,b,c]

and want to generate a list containing the Cartesian product of the two sets:

[
  [1,a], [1,b], [1,c],
  [2,a], [2,b], [2,c],
  [3,a], [3,b], [3,c],
]

The simplest way is to use findall/3 and member/2:

matrix( Xs, Ys, M ) :- findall( [X,Y] , ( member(X,Xs), member(Y,Ys) ) , M ).

And if you wanted to roll your own, it's not much more difficult. You might notice that we're using a helper predicate with an additional argument that will give us back the unbound tail of the list we're building, which gets closed when we run out of Xs.

Here's the code:

pairs( []     , _  , [] ) .  % Once we exhausted the Xs, we're done.
pairs( [X|Xs] , Ys , Ps ) :- % But if we have an X, then...
  pair(X,Ys,Ps, P0 ),        % - pair that X with every Y, and
  pairs(Xs,Ys,P0)            % - and recurse down
  .                          % Easy!

pair( _ , []     , Ps       , Ps ) .  % Once we've exhausted the Ys, we're done
pair( X , [Y|Ys] , [X:Y|Ps] , P0 ) :- % Otherwise, construct the X:Y pair, and
  pair(X,Ys,Ps,P0)                    % - recurse down.
  .                                   % Even easier!

Upvotes: 1

Related Questions