[GAP Forum] Iteration Over Lists of Lists

[Wolstenholme, Robert]

Thanks, this is what I wanted. 
However, I timed it this morning and found it to actually be slower than the method I previously mentioned (currently speed is of significant importance for what I'm doing). I've included the test script below. You can vary the values of `n` (number of lists) and `k` (size of lists). Note for `n=6` and `k=9` I am getting,

IteratorOfCartesianProduct Method: 452ms
My Mentioned Method                  : 203ms
Python for Reference                     : 066ms

I was hoping for something nearer the speed of the Python implementation.

Code (can be copied and pasted)
####################################################################################
n := 6;
k := 9;

############################
#IteratorOfCartesianProduct Method#
############################
lol := [];
for i in [1..n] do
    lol[i] := [1..k];
od;

a := 1;

start := Runtime();

for x in IteratorOfCartesianProduct(lol) do
    #a := a + 1;
	#Print("x: ", x, "\n");
od;

total1 := Runtime() - start;


###################
#My Mentioned Method#
###################
size_rc := List([1..n], x -> k);
base := List([1..n], x -> 1); #We store the iteration step state in base
a := 1;

start := Runtime();
repeat

	#Perform whatever list[i][base[i]] calculations here
	#a := a + 1;
	#Print("Base: ", base, "\n");

	#Execute the incrementor
	base[1] := base[1] + 1;
	for j in [2..n] do
		if base[j-1] = size_rc[j-1] + 1 then
				base[j] := base[j] + 1;
					base[j-1] := 1;
		fi;
	od;
until base[n] = size_rc[n] + 1;

total2 := Runtime() - start;

Print("\nTotal1: ", total1, "\nTotal2: ", total2);
####################################################################################

Thanks,
Rob

________________________________________
From: Alexander Konovalov [alexander.konovalov at gmail.com]
Sent: 16 January 2014 22:19
To: Wolstenholme, Robert
Cc: forum at mail.gap-system.org
Subject: Re: [GAP Forum] Iteration Over Lists of Lists

Very briefly (sorry, don't have time for a larger explanation today)
- in this case, see IteratorOfCartesianProduct. For example, after

   lists := [];
   lists[1] := [1,2,3];
   lists[2] := [4,5];

try this:

gap> for x in IteratorOfCartesianProduct(lists) do Print(x,"\n");od;
[ 1, 4 ]
[ 1, 5 ]
[ 2, 4 ]
[ 2, 5 ]
[ 3, 4 ]
[ 3, 5 ]

This iterates over the cartesian product without generating the list of all tuples from it, and should work fast enough.

Best wishes
Alexander



On 16 Jan 2014, at 22:13, "Wolstenholme, Robert" <robert.wolstenholme08 at imperial.ac.uk> wrote:

> Thanks for the reply. I don't think I was clear enough with my initial question though so have given the example below:
>
> ###################################################################################
> Consider
>
>    lists := []
>    lists[1] := [1,2,3]
>    lists[2] := [4,5]
>
> I would now like to iterate over the cartesian product of `lists[1]` and `lists[2]` i.e. `[[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]`.
>
> For an example this small, you could simply store the cartesian product itself in a list and iterate over that. This obviously becomes very inefficient if we have more lists with a larger number of values.
>
>
> A better way is, if we have `n` lists and `size_rc[i] := Size(list[i])`, we can avoid storing/calculating the Cartesian product with
>
>    base := List([1..n], x -> 1); #We store the iteration step state in base
>    while base <> size_rc do
>
>        #Perform whatever list[i][base[i]] calculations here
>
>        #Execute the incrementor
>        base[1] := base[1] + 1;
>            for j in [2..n] do
>                if base[j-1] = size_rc[j-1] + 1 then
>                        base[j] := base[j] + 1;
>                            base[j-1] := 1;
>                fi;
>            od;
>    od;
>
> then at each loop of the while `base` contains the values we need.
>
> However this is still far slower than the Python implementation I mentioned before. I was wondering if there was a way in GAP to speed up this iteration (maybe by pointing to the memory locations of the lists)?
>
> Thanks,
> Rob
>
> ________________________________________
> From: Alexander Konovalov [alexander.konovalov at gmail.com]
> Sent: 16 January 2014 22:01
> To: Wolstenholme, Robert
> Cc: forum at mail.gap-system.org
> Subject: Re: [GAP Forum] Iteration Over Lists of Lists
>
> On 16 Jan 2014, at 20:03, "Wolstenholme, Robert" <robert.wolstenholme08 at imperial.ac.uk> wrote:
>
>> Is there a way in GAP to 'quickly' iterate of lists of lists i.e. like the Python itertools.product() function?
>>
>
> Yes, see `21.20 Operations for Lists' from the GAP Reference Manual. You may enter `?Operations for Lists' in GAP or see it online at
>
>        http://www.gap-system.org/Manuals/doc/ref/chap21.html#X7DF510F7848CBBFD
>
> A random example just to expose the syntax and some functions:
>
> gap> l:=List([1..10],i -> [1..i]);
> [ [ 1 ], [ 1, 2 ], [ 1 .. 3 ], [ 1 .. 4 ], [ 1 .. 5 ], [ 1 .. 6 ],
>  [ 1 .. 7 ], [ 1 .. 8 ], [ 1 .. 9 ], [ 1 .. 10 ] ]
> gap> Sum( List( l, x -> Product( List( x, Fibonacci ) ) ) );
> 124819000
>
>
> HTH,
> Alexander
>
>
>
>