Prolog - finding all combinations (The product) of List of Lists (of Lists)

Question

I'v tried a few features to implement a predicate which finds all the combinations, like in that example:

List = [[1, 2], [1, 2, 3]]

These should be the output,

Comb = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]] 

but all the solutions I've found were using findall which I don't want to use in my task.

How can I differently implement the predicate, avoiding findall ?

Or maybe how can I implement my_findall without using any built-in features?

A solution like here, without built-in predicates would be great

Thanks to the helpers!

Answer 1

I'm not so sure this is the most efficient approach, but it's fairly transparent. The idea here is to define the problem in recursive (or inductive) "layers":

% multiply_lists(ListOfLists, MultipliedListOfLists)
%
% The first two clauses handle the case where ListOfLists consists
%   of just one list
% The third clause handles the general case
%
multiply_lists([[X]], [[X]]).
multiply_lists([[X|Xs]], [[X]|T]) :- 
    multiply_lists([Xs], T).
multiply_lists([E|Es], R) :-
    multiply_lists(Es, R1),
    multiply_list(E, R1, R).

% multiply_list relates the product of a list of lists and a single list
%    of elements
%
multiply_list([], _, []).
multiply_list([E|Es], L, Ls) :-
    multiply_list(Es, L, LL),
    multiply_element(E, L, LL, Ls).

% multiply_element relates the product, prepended to a given list,
%   of a single list of lists and a single element 
%
multiply_element(_, [], A, A).
multiply_element(X, [Y|Ys], A, [[X|Y]|T]) :-
    multiply_element(X, Ys, A, T).

multiply_element/4 actually combines two rules into one: it defines multiplication of a list by a single element, and prepends those results as individual elements to a given list.

A sample result:

| ?- multiply_lists([[1, 2], [1, 2, 3]], L).

L = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]] ? ;

no
| ?- multiply_lists([[a,b,c], [1,2], [x,y]], L).

L = [[a,1,x],[a,1,y],[a,2,x],[a,2,y],[b,1,x],[b,1,y],[b,2,x],[b,2,y],[c,1,x],[c,1,y],[c,2,x],[c,2,y]] ? ;

no

Some quirks with the above implementation:

• It's not tail recursive (so will use more stack as the lists get longer)
• It leaves a choice point

But it does illustrate how the problem can be solved without using append/3 or other list-based pre-defined predicates.

Answer 2

You could use the implementation of findall from "The Craft of Prolog". But in any way you will end up using built-in meta predicates.

So regarding your linked solution

try([],[]).
try([L|Ls],[M|Ms]):-
  member(M,L),
  try(Ls,Ms).

findall2( Template, Enumerator, List ) :-
  asserta( 'find all'( [] ) ),
  call( Enumerator ),
  asserta( 'find all'( {Template} ) ),
  fail
;
  all_found( [], List ).


all_found( SoFar, List ) :-
  retract('find all'( Item ) ),
  !,
  /*  to stop retract looking for more Items.  */
  all_found( Item, SoFar, List ).


all_found( [], List, List ).

all_found( {Template}, SoFar, List ) :-
  all_found( [Template|SoFar], List ).

So you will get

?- List = [[1, 2], [1, 2, 3]], findall2(M,try(List,M),Comb).
List = [[1, 2], [1, 2, 3]],
Comb = [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3]].