Combinations of multiple lists - Prolog

Question

I need to find the combinations in a list of lists. For example, give the following list,

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

These should be the output,

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

Another example:

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

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

I know how to do it for a list with two sublists but it needs to work for any number of sublists.

I'm new to Prolog, please help.

`List = [[1,2],[1,2],[1,2,3]], bagof(Es, maplist(member,Es,List), Ess).` — false, Mar 08 '20 at 14:05
@GuyCoder: Any extension that is based on a system that itself is not very much conforming is certainly rather suspicious. In case of difficulties one would have to consult the expanded Prolog below. — false, Mar 08 '20 at 19:15
@GuyCoder: So do you think that this would have been easy for OP? — false, Mar 09 '20 at 23:17
@GuyCoder: A reminder: you offered a trade. And I fulfilled my part. — false, Mar 10 '20 at 09:49

repeat · Answer 1 · 2020-04-01T12:12:00.113

This answer hunts the bounty offered "for a pure solution that also takes into account for Ess". Here we generalize this previous answer like so:

list_crossproduct(Xs, []) :-
   member([], Xs).
list_crossproduct(Xs, Ess) :-
   Ess = [E0|_],
   same_length(E0, Xs),
   maplist(maybelonger_than(Ess), Xs),
   list_comb(Xs, Ess).

maybelonger_than(Xs, Ys) :-
   maybeshorter_than(Ys, Xs).

maybeshorter_than([], _).
maybeshorter_than([_|Xs], [_|Ys]) :-
   maybeshorter_than(Xs, Ys).

list_crossproduct/2 gets bidirectional by relating Xs and Ess early.

?- list_comb(Xs, [[1,2,3],[1,2,4],[1,2,5]]).
nontermination                                % BAD!

?- list_crossproduct(Xs, [[1,2,3],[1,2,4],[1,2,5]]).
   Xs = [[1],[2],[3,4,5]]      % this now works, too
;  false.

Sample query having multiple answers:

?- list_crossproduct(Xs, [[1,2,3],[1,2,4],[1,2,5],X,Y,Z]).
   X = [1,2,_A],
   Y = [1,2,_B],
   Z = [1,2,_C], Xs = [[1],[2],[3,4,5,_A,_B,_C]]
;  X = [1,_A,3],
   Y = [1,_A,4],
   Z = [1,_A,5], Xs = [[1],[2,_A],[3,4,5]]
;  X = [_A,2,3],
   Y = [_A,2,4],
   Z = [_A,2,5], Xs = [[1,_A],[2],[3,4,5]]
;  false.

Of interest: better use `nilmemberd(Xs)` instead of `member([],Xs)`. — repeat, Mar 26 '20 at 19:20

score 2 · Answer 2 · edited Mar 12 '20 at 22:44

2

For completeness, here is the augmented version of my comment-version. Note nilmemberd_t/2 which is inspired by memberd_t/2.

nilmemberd_t([], false).
nilmemberd_t([X|Xs], T) :-
   if_(nil_t(X), T = true, nilmemberd_t(Xs, T)).

nil_t([], true).
nil_t([_|_], false).

list_comb(List, []) :-
   nilmemberd_t(List, true).
list_comb(List, Ess) :-
   bagof(Es, maplist(member,Es,List), Ess).

Above version shows that "only" the first clause was missing in my comment response. Maybe even shorter with:

nilmemberd([[]|_]).
nilmemberd([[_|_]|Nils]) :-
   nilmemberd(Nils).

This should work for Prologs without constraints. With constraints, bagof/3 would have to be reconsidered since copying constraints is an ill-defined terrain.

edited Mar 12 '20 at 22:44

repeat

18,496
4
54
166

answered Mar 12 '20 at 20:05

false

10,264
13
101
209

1

@rep: you mean you qualify for the promised bounty? – false Mar 13 '20 at 01:10
1

Nah! But I reckon I should post a lambda variant as a separate answer. (just 4 fun, not bounty worthy) – repeat Mar 13 '20 at 16:18
presumably, you did all these instead of just using `findall` instead of the `bagof`, to avoid the `findall( Es, maplist( member,Es, [[1,2],t,[1]]), Ess).` incorrectly succeeding with `[]` instead of failing. but your version also similarly incorrectly succeeds with `[]` for `[[1,2],[],t,[1]]`. – Will Ness Mar 23 '20 at 08:20
I mean, because `bagof` incorrectly fails on `[[1,1],[],[1]]`, yet `findall` correctly (in this case) succeeds with `[]`. – Will Ness Mar 23 '20 at 08:31
1

@Will: `bagof/3` handles variables correctly whereas `findall/3` copies them like mad – false Mar 23 '20 at 20:58
`list_comb([[1,2],[],t,[1]],X).` `list_comb(T,[[1]]).` – Will Ness Mar 24 '20 at 08:29
That `list_comb(T,[[1]]).` loops is a much lesser problem than when it would fail, as looping cannot be interpreted as being true or false. And for `list_comb([[1,2],[],t,[1]],X).`: If you see this generalization as a problem, why do you then also choose to succeed for `list_comb([[1|non_list]],X)`? To me this appears as acceptable, But if you insist please throw in `maplist(maplist(\_^true), List)` at the end of both rules. – false Mar 24 '20 at 11:20
I've just tried `list_comb( [[1 | t]], X ).` with my code and *it properly fails as expected*. – Will Ness Mar 26 '20 at 12:32
@WillNess: Agreed. – false Mar 26 '20 at 12:37

repeat · Answer 3 · 2020-03-23T19:21:32.457

Here's a way to do it using maplist/3 and append/2:

list_comb([], [[]]).
list_comb([Xs|Xss], Ess) :-
   Xs = [_|_],
   list_comb(Xss, Ess0),
   maplist(aux_x_comb(Ess0), Xs, Esss1),
   append(Esss1, Ess).

aux_x_comb(Ess0, X, Ess1) :-
   maplist(head_tail_list(X), Ess0, Ess1).

head_tail_list(X, Xs, [X|Xs]).

Sample query:

?- list_comb([[a,b],[f,g],[x,y,z]], Ess).
Ess = [[a,f,x],[a,f,y],[a,f,z],
       [a,g,x],[a,g,y],[a,g,z],
       [b,f,x],[b,f,y],[b,f,z],
       [b,g,x],[b,g,y],[b,g,z]].

Here's how it works! As an example, consider these goals:

list_comb([[a,b],[f,g],[x,y,z]], Ess)
list_comb([ [f,g],[x,y,z]], Ess0)

How can we get from Ess0 to Ess?

We look at the answers to the latter query:

?- list_comb([[f,g],[x,y,z]], Ess0).
Ess0 = [[f,x],[f,y],[f,z], [g,x],[g,y],[g,z]].

... place a before [f,x], ..., [g,z] ...

?- maplist(head_tail_list(a),
           [[f,x],[f,y],[f,z],
            [g,x],[g,y],[g,z]], X).
X = [[a,f,x],[a,f,y],[a,f,z],
     [a,g,x],[a,g,y],[a,g,z]].

... then do the same for b.

maplist(aux_x_comb) helps us handle all items:

?- maplist(aux_x_comb([[f,x],[f,y],[f,z],
                       [g,x],[g,y],[g,z]]),
           [a,b], X).
X = [[[a,f,x],[a,f,y],[a,f,z],
      [a,g,x],[a,g,y],[a,g,z]],
     [[b,f,x],[b,f,y],[b,f,z],
      [b,g,x],[b,g,y],[b,g,z]]].

To get from a list of lists to a list use append/2.

I hope this explanation was more eludicating than confusing:)

`Ess` has no influence on termination - at least in some case — false, Mar 16 '20 at 22:08

Will Ness · Answer 4 · 2020-08-23T06:45:48.487

0

A twist in @false's approach:

%list_comb( ++LL, -Ess)
list_comb( LL, Ess):-
    is_list( LL),
    maplist( is_list, LL),
    findall( Es, maplist( member, Es, LL), Ess).

Testing:

41 ?- list_comb( [[1,2],[1],[1]], X).
X = [[1, 1, 1], [2, 1, 1]].

42 ?- list_comb( [[1,2],[1],[1,2,3]], X).
X = [[1, 1, 1], [1, 1, 2], [1, 1, 3], [2, 1, 1], [2, 1, 2], [2, 1, 3]].

43 ?- list_comb( [[1,2],[],[1,2,3]], X).
X = [].

44 ?- list_comb( [[1,2],t,[1,2,3]], X).
false.

45 ?- list_comb( t, X).
false.

edited Aug 23 '20 at 06:45

answered Mar 23 '20 at 08:44

Will Ness

70,110
9
98
181

2

By ruling out variables, the predicate becomes moded like a functional program - but without la... - er - non-strictness. – false Mar 24 '20 at 11:11

Combinations of multiple lists - Prolog

4 Answers4

Linked

Related