[GAP Forum] cartesian product

[Alexander Konovalov]

Dear Inneke,

I can provide temporary workaround for this, which will work with GAP  
4.4.10.
This is expected to appear in one of the future versions of GAP.

1) Create a file "iterator.gd" with the following content (and observer
the description in the comments (it has GAPDoc format, please ask me if
you will need further explanations):

#############################################################################
##
#F  IteratorOfCartesianProduct( list1, list2, ... )
#F  IteratorOfCartesianProduct( list )
##
##  <#GAPDoc Label="IteratorOfCartesianProduct">
##  <ManSection>
##  <Func Name="IteratorOfCartesianProduct" Arg='list1, list2 ...'/>
##  <Func Name="IteratorOfCartesianProduct" Arg='list'/>
##
##  <Description>
##  In the first form <C>IteratorOfCartesianProduct</C> returns
##  an iterator (see&nbsp;<Ref Sect="Iterators"/>) of all elements
#   of the cartesian product (see&nbsp;<Ref Func="Cartesian"/>)
#   of the lists <A>list1</A>, <A>list2</A>, etc.
##  <P/>
##  In the second form <A>list</A> must be a list of lists
##  <A>list1</A>, <A>list2</A>, etc., and  
<C>IteratorOfCartesianProduct</C>
##  returns an iterator of the cartesian product of those lists.
##  <P/>
##  Resulting tuples will be returned in the lexicographic order.
##  Usage of iterators of cartesian products is recommended in the
##  case when the resulting cartesian product is big enough, so its
##  generating and storage will require essential amount of runtime
##  and memory. For smaller cartesian products it is faster to
##  generate the full set of tuples using <Ref Func="Cartesian"/>
##  and then loop over its elements (with some minor overhead of needing
##  more memory).
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "IteratorOfCartesianProduct" );

2) Create a file "iterator.gi" with the following content:

#############################################################################
##
#F  IteratorOfCartesianProduct( list1, list2, ... )
#F  IteratorOfCartesianProduct( list )
##
##  All elements of the cartesian product of lists
##  <list1>, <list2>, ... are returned in the lexicographic order.
##
BindGlobal( "IsDoneIterator_Cartesian", iter -> ( iter!.next =  
false ) );

BindGlobal( "NextIterator_Cartesian",
     function( iter )
     local succ, n, sets, res, i, k;
     succ := iter!.next;
     n := iter!.n;
     sets := iter!.sets;
     res := [];
     i := n;
     while i > 0 do
       res[i] := sets[i][succ[i]];
       i := i-1;
     od;

     if succ = iter!.sizes then
       iter!.next := false;
     else
       succ[n] := succ[n] + 1;
       for k in [n,n-1..2] do
         if succ[k] > iter!.sizes[k] then
           succ[k] := 1;
           succ[k-1] := succ[k-1] + 1;
         else
           break;
         fi;
       od;
     fi;

     return res;
     end);

BindGlobal( "ShallowCopy_Cartesian",
             iter -> rec(
                      sizes := iter!.sizes,
                          n := iter!.n,
                       next := ShallowCopy( iter!.next ) ) );

BindGlobal( "IteratorOfCartesianProduct2",
     function( listsets )
     local s, n, x;
     if not ForAll( listsets, IsCollection ) and ForAll( listsets,  
IsFinite ) then
       Error( "Each arguments must be a finite collection" );
     fi;
     s := List( listsets, Set );
     n := Length( s );
     # from now s is a list of n finite sets
     return IteratorByFunctions(
       rec( IsDoneIterator := IsDoneIterator_Cartesian,
            NextIterator   := NextIterator_Cartesian,
            ShallowCopy    := ShallowCopy_Cartesian,
            sets           := s,                      # list of sets
            sizes          := List( s, Size ),        # sizes of sets
            n              := n,                      # number of sets
            nextelts       := List( s, x -> x[1] ),   # list of 1st  
elements
            next           := 0 * [ 1 .. n ] + 1 ) ); # list of 1's
     end);

InstallGlobalFunction( "IteratorOfCartesianProduct",
     function( arg )
     # this mimics usage of functions Cartesian and Cartesian2
     if Length( arg ) = 1  then
         return IteratorOfCartesianProduct2( arg[1] );
     else
         return IteratorOfCartesianProduct2( arg );
     fi;
     return;
     end);

3) Read first gd-file and then gi-file (assuming that they are in the
current directory, otherwise state full path to the file):

gap> Read("iterator.gd");
gap> Read("iterator.gi");

4) Now you can do the following:

gap> it:=IteratorOfCartesianProduct([1,2],[3,4]);
<iterator>
gap> for i in it do Print(i,"\n");od;
[ 1, 3 ]
[ 1, 4 ]
[ 2, 3 ]
[ 2, 4 ]

or

gap> it:=IteratorOfCartesianProduct([[1,2],["a","b"]]);
<iterator>
gap> for i in it do Print(i,"\n");od;
[ 1, "a" ]
[ 1, "b" ]
[ 2, "a" ]
[ 2, "b" ]

i.e. you may have one argument that is a list of lists,
or N arguments, each being a list.

5) You may read these two files in the beginning of your GAP
session, putting appropriate commands in the gaprc file
(type ?.gaprc in the GAP prompt to see the documentation).
You shouldn't re-read them each time when you reread your
own code.

Hope this is just what you need!

Best wishes,
Alexander


On 29 Nov 2007, at 12:01, Inneke Van Gelder wrote:

> Hi,
>
>
>
>
>
> I need to compute the Cartesian product of an arbitrary number of  
> sets and
> test the members of the Cartesian product to some conditions. But  
> only a few
> satisfy the conditions. My problem is that I exceed the permitted  
> memory to
> soon. Is there a way to compute the Cartesian product member by  
> member and
> test before saving? If the number of sets is known, it isn't  
> difficult,
> because you can avoid recursion. But what about an arbitrary number  
> of sets?
>
>
>
>
>
> Thanks for helping,
>
>
>
> Inneke