Cartesian product of lists
Ivan Shmakov
into the Cartesian product (a kind of) of these lists, like:
?- cartprod([[1, 2, 3], [1, 10, 100]], R).
R = [[1, 1], [1, 10], [1, 100], [2, 1], [2, 10], [2, 100]|...].
?-
Having found none among the SWI-Prolog's built-in and library
predicates (or are there any other libraries I should've
checked?), I was able to code the following.
Is it just as simple?
Impressive.
cartprod(LOL, RES) :-
cartprod(LOL, RES, []).
cartprod([], TAIL, TAIL).
cartprod(LOL, RES, TAIL) :-
L2 = [L2H | L2T],
L2T = [_ | _],
(
append([L1, [L2], L3], LOL) ->
append([L1, [L2T], L3], LLT),
cartprod(LLT, RIM, TAIL),
append([L1, [[L2H]], L3], LLH),
cartprod(LLH, RES, RIM) ;
findall(X, member([X], LOL), L),
RES = [L | TAIL]
).
--
FSF associate member #7257
k...@kymhorsell.com
> Today, my quest was for a predicate to transform a list of lists
> into the Cartesian product (a kind of) of these lists, like:
> ?- cartprod([[1, 2, 3], [1, 10, 100]], R).
> R = [[1, 1], [1, 10], [1, 100], [2, 1], [2, 10], [2, 100]|...].
Perhaps even simpler if you use bagof as in
cartprod(L1,L2,Res) :- bagof([X,Y],(member(X,L1),member(Y,L2)),Res).
--
The slow rise of sea level is caused by rain. Water transfer the soil to see.
The acceleration during the last 50 years is caused by using gas and oil
instead of coal. Gas and oil are changed into water during combustion.
So the slow or the accelerated rise of sea level is not a problem.
-- Szczepan Bialek <sz.b...@wp.pl>, 28 May 2011 09:50 +0200
Ivan Shmakov
>> Today, my quest was for a predicate to transform a list of lists
>> into the Cartesian product (a kind of) of these lists, like:
>> ?- cartprod([[1, 2, 3], [1, 10, 100]], R).
>> R = [[1, 1], [1, 10], [1, 100], [2, 1], [2, 10], [2, 100]|...].
> ...
> Perhaps even simpler if you use bagof as in
> cartprod(L1,L2,Res) :- bagof([X,Y],(member(X,L1),member(Y,L2)),Res).
Can this code be generalized for the case of any number of input
lists?
Jussi Piitulainen
Best thus, I think:
prod(Ls, P) :-
bagof(Xs, members(Xs, Ls), P).
members([], []).
members([E|Es], [L|Ls]) :-
member(E, L),
members(Es, Ls).
I'd like to see it in terms of nested bagofs if there is a way. I got
confused trying.
Bart Demoen
> Ivan Shmakov <iv...@gray.siamics.net> writes:
> prod(Ls, P) :-
> bagof(Xs, members(Xs, Ls), P).
>
> members([], []).
> members([E|Es], [L|Ls]) :-
> member(E, L),
> members(Es, Ls).
>
> I'd like to see it in terms of nested bagofs if there is a way. I got
> confused trying.
Would this qualify ?
prod([],[[]]).
prod([L|Ls],Out) :-
bagof([X|R],(prod(Ls,O), member(X,L), member(R,O)),Out).
Cheers
Bart Demoen
--- Posted via news://freenews.netfront.net/ - Complaints to ne...@netfront.net ---
Jussi Piitulainen
> On Thu, 30 Jun 2011 17:51:48 +0300, Jussi Piitulainen wrote:
>
> > Ivan Shmakov <iv...@gray.siamics.net> writes:
>
> > prod(Ls, P) :-
> > bagof(Xs, members(Xs, Ls), P).
> >
> > members([], []).
> > members([E|Es], [L|Ls]) :-
> > member(E, L),
> > members(Es, Ls).
> >
> > I'd like to see it in terms of nested bagofs if there is a way. I got
> > confused trying.
>
> Would this qualify ?
>
> prod([],[[]]).
> prod([L|Ls],Out) :-
> bagof([X|R],(prod(Ls,O), member(X,L), member(R,O)),Out).
It seems to match what I meant to ask :) Thank you.
Ivan Shmakov
>>>>> Ivan Shmakov <iv...@gray.siamics.net> writes:
>>>>> kym <k...@kymhorsell.com> writes:
[…]
>>> cartprod(L1,L2,Res) :- bagof([X,Y],(member(X,L1),member(Y,L2)),Res).
>> Can this code be generalized for the case of any number of
>> input lists?
> Best thus, I think:
> prod(Ls, P) :-
> bagof(Xs, members(Xs, Ls), P).
> members([], []).
> members([E|Es], [L|Ls]) :-
> member(E, L),
> members(Es, Ls).
Or, maplist/3 from SWI's library(apply) could be used here:
yprod(LOL, RES) :-
bagof(LOE, maplist(member, LOE, LOL), RES).
Thanks!
[…]
k...@kymhorsell.com
Only in principle. :)
--
[A]ll science is lies and the only thing we can trust is right wing rhetoric.
-- BONZO@27-32-240-172 [100 nyms and counting], 14 Jan 2011 14:46 +1100
Feliks
> > >> Today, my quest was for a predicate to transform a list of lists
> > >> into the Cartesian product (a kind of) of these lists, like:
> > >> ?- cartprod([[1, 2, 3], [1, 10, 100]], R).
> > >> R = [[1, 1], [1, 10], [1, 100], [2, 1], [2, 10], [2, 100]|...].
> > > ...
> > > Perhaps even simpler if you use bagof as in
> > > cartprod(L1,L2,Res) :- bagof([X,Y],(member(X,L1),member(Y,L2)),Res).
> > Can this code be generalized for the case of any number of input
> > lists?
>
> Only in principle. :)
>
> --
> [A]ll science is lies and the only thing we can trust is right wing rhetoric.
> -- BONZO@27-32-240-172 [100 nyms and counting], 14 Jan 2011 14:46 +1100
Why should we use findall or bagof, which is heavy machinery indeed?
The following does the trick:
cartesian_product( Set1, Set2, Product ) :-
maplist( prod( Set1 ), Set2, Product ).
prod( Set, Element, Tuples ) :-
maplist( mk_pair( Element ), Set, Tuples ).
mk_pair( A, B, [ A, B ] ).
(Not that this is the best way to represent pairs, but that is another
question.)
I leave generalisation as an exercise. :-)
-- Feliks
afa
> Today, my quest was for a predicate to transform a list of lists
> into the Cartesian product (a kind of) of these lists, like:
>
> ?- cartprod([[1, 2, 3], [1, 10, 100]], R).
> R = [[1, 1], [1, 10], [1, 100], [2, 1], [2, 10], [2, 100]|...].
How is this one (in B-Prolog)?
cartprod([L1,L2],R):-!,
R @= [[X1,X2] : X1 in L1, X2 in L2].
cartprod([L|Ls],R):-
cartprod(Ls,R1),
R @= [[X|P] : X in L, P in R1].
It's short and should be much faster than the one that uses bagof.
Cheers,
Neng-Fa
Feliks
> > >> Today, my quest was for a predicate to transform a list of lists
> > >> into the Cartesian product (a kind of) of these lists, like:
> > >> ?- cartprod([[1, 2, 3], [1, 10, 100]], R).
> > >> R = [[1, 1], [1, 10], [1, 100], [2, 1], [2, 10], [2, 100]|...].
> > > ...
> > > Perhaps even simpler if you use bagof as in
> > > cartprod(L1,L2,Res) :- bagof([X,Y],(member(X,L1),member(Y,L2)),Res).
> > Can this code be generalized for the case of any number of input
> > lists?
>
> Only in principle. :)
>
> --
> [A]ll science is lies and the only thing we can trust is right wing rhetoric.
> -- BONZO@27-32-240-172 [100 nyms and counting], 14 Jan 2011 14:46 +1100
(This is a repetition: the previous post seems to have disappeared.)
Why use bagof/3? This is heavy machinery.
The following should do the trick:
cartesian_poduct( Set1, Set2, Product ) :-
maplist( prod( Set1 ), Set1, Product ).
prod( Set, Element, Tuples ) :-
maplist( mk_tuple( Element ), Set, Tuples ).
mk_tuple( A, B, [ A, B ] ).
(Not the best way to represent a tuple, but this one was specified.)
-- Feliks
k...@kymhorsell.com
...
> Why should we use findall or bagof, which is heavy machinery indeed?
In the context of "newbies" -- pedagogy. But don't you worry about it. :)
--
We believe there is not enough uranium production, either current or planned, to
satisfy reactor needs, initial core requirements and inventories for new reactors.
-- Adam Schatzker, analyst RBC Capital Markets
Jan Wielemaker
> Feliks <feliks....@utdallas.edu> wrote:
> ...
>> Why should we use findall or bagof, which is heavy machinery indeed?
> ...
>
> In the context of "newbies" -- pedagogy. But don't you worry about it. :)
I don't know. While trying to teach newbies some simple techniques to
bluf their way into doing something useful with Prolog, I often
advocated a strategy to create simple small rules that generated and put
conditions on the results and then use findall/etc to collect the
result. That works quite well as long as the (intermediate) results are
ground terms. Once variables sneek in, these predicates become much more
complicated to understand. With constraints, it becomes even worse.
Another disadvantage is that, while many findall/bagof constructs can
trivially be rewritten, it is generally not possible to do this automatically
because the difference between copying and not copying often doesn't matter,
but it might matter.
Cheers --- Jan
Ivan Shmakov
[…]
> Why should we use findall or bagof, which is heavy machinery indeed?
I'm not sure as to wheather it's heavy and why, yet it implies
copying of terms, which is contrary to my needs.
[…]
> mk_pair( A, B, [ A, B ] ).
> (Not that this is the best way to represent pairs, but that is
> another question.)
Any better choice? A functor?
> I leave generalisation as an exercise. :-)
The best I've managed to get from maplist/3 (before
understanding that it won't append/3 lists for me) is:
cartprod([], [[]]).
cartprod([L | LOL], RES) :-
cartprod(LOL, RIM),
maplist(cartprod1(L), RIM, RES).
cartprod1(L, TAIL, RES) :-
maplist(xcons(TAIL), L, RES).
xcons(A, B, [B | A]).
Which isn't quite the thing I need.
However, I was successful when I've switched to rfold/4 instead:
?- cartprod([[1, 2], [a, b], [X, Y]], RES),
length(RES, LEN).
RES = [[1, a, X], [2, a, X], [1, b, X], [2, b, X], [1, a, Y], [2, a, Y]|...],
LEN = 8.
?-
rfold(PRED, [], RES, RES) :-
!.
rfold(PRED, [H | T], INIT, RES) :-
rfold(PRED, T, INIT, RIM),
call(PRED, RIM, H, RES).
cartprod([], [[]]).
cartprod([L | LOL], RES) :-
cartprod(LOL, RIM),
rfold(cartprod1(L), RIM, [], RES).
cartprod1([], RES, _, RES) :-
!.
cartprod1([H | T], OLD, TAIL, NEW) :-
cartprod1(T, OLD, TAIL, NIM),
NEW = [[H | TAIL] | NIM].
Thanks!
Mats Carlsson
> Today, my quest was for a predicate to transform a list of lists
> into the Cartesian product (a kind of) of these lists, like:
>
> ?- cartprod([[1, 2, 3], [1, 10, 100]], R).
> R = [[1, 1], [1, 10], [1, 100], [2, 1], [2, 10], [2, 100]|...].
Here is a solution for SICStus:
cartprod(LOL, Res) :-
cartprod(LOL, [[]], Res).
cartprod([], Res, Res).
cartprod([L1|Ls], Res0, Res) :-
cartprod(Ls, Res0, Res1),
cartprod(L1, Res1, Res, []).
cartprod(L1, Res1) -->
( foreach(X1,L1),
param(Res1)
do ( foreach(R1,Res1),
param(X1)
do [[X1|R1]]
)
).
Ulrich Neumerkel
>Here is a solution for SICStus:
There is a subtle anomaly in this solution and the corresponding
intuitive expansion. Using ECLiPSe:
[eclipse 3]: X = 1, Xs = [2], cartprod([[X|Xs]],R).
X = 1
Xs = [2]
R = [[1], [2]]
Yes (0.00s cpu)
[eclipse 4]: cartprod([[X|Xs]],R), X = 1, Xs = [2].
No (0.00s cpu)
[eclipse 5]: cartprod([[X|Xs]],R).
X = X
Xs = []
R = [[X]]
Yes (0.00s cpu)