8.8 Cartesian product as a list (1.7.02)

8.8.1 Naser Hosseini

I am using Maple V, generating a cartesian product.

I would like to access the members of the product like I can access the members of a list.

8.8.2 Carl Devore (23.7.02)

The command combinat[cartprod] returns an iterator that generates a Cartesian product one element at a time.

The benefit of this is that the entire Cartesian product does not to be stored in memory.

But what if you want the entire Cartesian product as a single list? One option is just to call the iterator repeatedly to generate a list:

> CartProdDeiterated:= proc(L::list({list,set})) 
>    local C,i,S; 
>    C:= combinat[cartprod](L); 
>    [seq(C[nextvalue](), i= 1..mul(nops(S), S= L))] 
> end proc:
 

Example:

> A:= {1,2,3}:  B:= {4,5}: 
> CartProdDeiterated([A,B]); 
           [[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]]
 

But this is inefficient. After all, the iterator was designed to save memory at the expense of some processor time.

Using some elementary number theory, we can get an efficient Cartesian product. The ‘q‘ in the procedure below represents a multi-base integer.

The base at each digit position is the number of elements in the corresponding set factor.

The "digits" are extracted with quotients and remainders. Each digit is one less than the current position in the corresponding set.

Since Maple’s seq and irem commands act at lower level than do-loops, this is far faster than trying to do the same things with do-loops.

The procedure below runs in about half the time of the procedure above. It might also be beneficial if this technique was incorporated into combinat[cartprod].

> CartProdAsList:= proc(L::list({list,set})) 
>    option `Copyright (C) 2002, Carl DeVore.  All rights reserved.`; 
>    local q,i,n,N; 
>    n:= nops(L); 
>    N:= map(nops, L); 
>    [seq([seq(L[i][1+irem(q,N[i],'q')], i= 1..n)], q= 0..`*`(N[])-1)] 
> end:
 

Note that with nested seq’s – unlike for loops – changing the value of the outer index in the inner loop does not cause any problem.

I tested this in Maple 6 and 8; I am not sure not it will work in Maple 5.

Also, I am not sure if iterated indexing (L[i][...]) will work in Maple 4.

> CartProdAsList([A,B]); 
           [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5]] 
 
> time(CartProdAsList([ [1,2,3] $ 11])); 
                                7.141 
 
> time(CartProdDeiterated( [ [1,2,3] $ 11])); 
                                17.875
 

Both of the procedures above take more than twice the time in Maple 6 as Maple 8.

So, so much for those who say that the later versions of Maple are slower.

8.8.3 Helmut Kahovec (28.7.02)

Well, besides Carl Devore’s procedure you may also try to use my Cartesian product operator, which I teach my students:

> `&x`:=proc() 
  option `Copyright (C) 2001, Helmut Kahovec. All rights reserved.`; 
    if type([args],list(list)) then 
      if nargs>2 then 
        procname( 
          procname(args[1],args[2]), 
          args[3..-1] 
        ) 
      else 
        [ 
          seq( 
            seq( 
              [ 
                `if`(type(i,list),op(i),i), 
                `if`(type(j,list),op(j),j) 
              ], 
              j=args[2] 
            ), 
            i=args[1] 
          ) 
        ] 
      end if 
    else 
      error "sequence of lists expected" 
    end if 
  end proc:
 

> [1,2,3]&x[1,2,3]; 
 
  [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], 
        [3, 3]] 
 
> time(`&x`([1,2,3]$11)); 
                                44.053 
 
> restart; 
> CartProdAsList:= proc(L::list({list,set})) 
  option `Copyright (C) 2002, Carl DeVore. All rights reserved.`; 
     local q,i,n,N; 
     n:= nops(L); 
     N:= map(nops, L); 
     [seq([seq(L[i][1+irem(q,N[i],'q')], i= 1..n)], q= 0..`*`(N[])-1)] 
  end: 
> CartProdAsList([[1,2,3]$2]); 
 
  [[1, 1], [2, 1], [3, 1], [1, 2], [2, 2], [3, 2], [1, 3], [2, 3], 
        [3, 3]] 
 
> time(CartProdAsList([[1,2,3]$11])); 
                                64.742