How to do Cartesian products in GP

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

Dear PARI users,

I am sometimes asked how to do Cartesian product of lists in PARI,
so here some ways:

1) simple Cartesian product.
A=[1,2,3];
B=[4,5,6]; 
AB=[[a,b]| a<-A; b<-B]
%3 = [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

(remember, you have to use a semi-colon before b<-B)

2) mapped Cartesian product.
Of course you can do
AB=[f(a,b)| a<-A; b<-B]
for any function of arity 2.
AB=[a*b| a<-A; b<-B]
%4 = [4,5,6,8,10,12,12,15,18]

3) multiple Cartesian products
C=[7,8,9];
ABC=[[a,b,c]| a<-A; b<-B; c<-C]
%6 = [[1,4,7],[1,4,8],[1,4,9],[1,5,7],[1,5,8],[1,5,9],[1,6,7],[1,6,8],[1,6,9]
     ,[2,4,7],[2,4,8],[2,4,9],[2,5,7],[2,5,8],[2,5,9],[2,6,7],[2,6,8],[2,6,9]
     ,[3,4,7],[3,4,8],[3,4,9],[3,5,7],[3,5,8],[3,5,9],[3,6,7],[3,6,8],[3,6,9]]

4) multiple mapped Cartesian products
[a*b+c| a<-A; b<-B; c<-C]
%7 = [11,12,13,12,13,14,13,14,15,15,16,17,17,18,19,19,20,21,19,20,21,22,23,24
     ,25,26,27]

5) variable number of Cartesian products
Let f(a,b) be an associative function, says
f(a,b)=a*b;
We define
F(A,B)=[f(a,b)| a<-A; b<-B];
Let L be a list of lists.
L=[A,B,C];
We will use fold:
fold(F,L)
%11 =
[28,32,36,35,40,45,42,48,54,56,64,72,70,80,90,84,96,108,84,96,108,105,120,135,126,144,162]
which is the same as
[a*b*c| a<-A; b<-B; c<-C]
except that L can be arbitrary long.

for standard Cartesian product, you can define

F(A,B)=[concat(a,b)| a<-A; b<-B]
fold(F,apply(S->[[s]|s<-S],L))
%13 = [[1,4,7],[1,4,8],[1,4,9],[1,5,7],[1,5,8],[1,5,9],[1,6,7],[1,6,8],[1,6,9],[2,4,7],[2,4,8],[2,4,9],[2,5,7],[2,5,8],[2,5,9],[2,6,7],[2,6,8],[2,6,9],[3,4,7],[3,4,8],[3,4,9],[3,5,7],[3,5,8],[3,5,9],[3,6,7],[3,6,8],[3,6,9]]

6) restricted Cartesian product

It is possible to restrict the Cartesian product with arbitrary
conditions:
[[a,aa]| a<-A; aa<-A, a<aa]
%15 = [[1,2],[1,3],[2,3]]
[[a,b]| a<-A; b<-B, isprime(a+b)]
%16 = [[1,4],[1,6],[2,5],[3,4]]

(remember, you have to use a comma before the condition)

Cheers,
Bill.