1.15 About Loops

Given a list pp of permutations we can form their product by means of a for loop instead of writing down the product explicitly.

    gap> pp:= [ (1,3,2,6,8)(4,5,9), (1,6)(2,7,8)(4,9), (1,5,7)(2,3,8,6),
    >           (1,8,9)(2,3,5,6,4), (1,9,8,6,3,4,7,2) ];;
    gap> prod:= ();
    ()
    gap> for p in pp do
    >       prod:= prod * p;
    >    od;
    gap> prod;
    (1,8,4,2,3,6,5) 

First a new variable prod is initialized to the identity permutation (). Then the loop variable p takes as its value one permutation after the other from the list pp and is multiplied with the present value of prod resulting in a new value which is then assigned to prod.

The for loop has the following syntax.

for var in list do statements od;

The effect of the for loop is to execute the statements for every element of the list. A for loop is a statement and therefore terminated by a semicolon. The list of statements is enclosed by the keywords do and od (reverse do). A for loop returns no value. Therefore we had to ask explicitly for the value of prod in the preceding example.

The for loop can loop over any kind of list, even a list with holes. In many programming languages (and in former versions of GAP, too) the for loop has the form

for var from first to last do statements od;

But this is merely a special case of the general for loop as defined above where the list in the loop body is a range.

for var in [first..last] do statements od;

You can for instance loop over a range to compute the factorial 15! of the number 15 in the following way.

    gap> ff:= 1;
    1
    gap> for i in [1..15] do
    >       ff:= ff * i;
    >    od;
    gap> ff;
    1307674368000 

The following example introduces the while loop which has the following syntax.

while condition do statements od;

The while loop loops over the statements as long as the condition evaluates to true. Like the for loop the while loop is terminated by the keyword od followed by a semicolon.

We can use our list primes to perform a very simple factorization. We begin by initializing a list factors to the empty list. In this list we want to collect the prime factors of the number 1333. Remember that a list has to exist before any values can be assigned to positions of the list. Then we will loop over the list primes and test for each prime whether it divides the number. If it does we will divide the number by that prime, add it to the list factors and continue.

    gap> n:= 1333;
    1333
    gap> factors:= [];
    [  ]
    gap> for p in primes do
    >       while n mod p = 0 do
    >          n:= n/p;
    >          Add(factors, p);
    >       od;
    >    od;
    gap> factors;
    [ 31, 43 ]
    gap> n;
    1 

As n now has the value 1 all prime factors of 1333 have been found and factors contains a complete factorization of 1333. This can of course be verified by multiplying 31 and 43.

This loop may be applied to arbitrary numbers in order to find prime factors. But as primes is not a complete list of all primes this loop may fail to find all prime factors of a number greater than 2000, say. You can try to improve it in such a way that new primes are added to the list primes if needed.

You have already seen that list objects may be changed. This holds of course also for the list in a loop body. In most cases you have to be careful not to change this list, but there are situations where this is quite useful. The following example shows a quick way to determine the primes smaller than 1000 by a sieve method. Here we will make use of the function Unbind to delete entries from a list.

    gap> primes:= [];
    [  ]
    gap> numbers:= [2..1000];
    [ 2 .. 1000 ]
    gap> for p in numbers do
    >       Add(primes, p);
    >       for n in numbers do
    >          if n mod p = 0 then
    >             Unbind(numbers[n-1]);
    >          fi;
    >       od;
    >    od; 

The inner loop removes all entries from numbers that are divisible by the last detected prime p. This is done by the function Unbind which deletes the binding of the list position numbers[n-1] to the value n so that afterwards numbers[n-1] no longer has an assigned value. The next element encountered in numbers by the outer loop necessarily is the next prime.

In a similar way it is possible to enlarge the list which is looped over. This yields a nice and short orbit algorithm for the action of a group, for example.

In this section you have learned how to loop over a list by the for loop and how to loop with respect to a logical condition with the while loop. You have seen that even the list in the loop body can be changed.

The for loop is described in For. The while loop is described in While.

Previous Up Top Next
Index