%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A list.tex GAP documentation Martin Schoenert %% %A @(#)$Id: list.tex,v 3.20 1994/05/30 14:52:25 vfelsch Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes the functions that mainly deal with lists. %% %H $Log: list.tex,v $ %H Revision 3.20 1994/05/30 14:52:25 vfelsch %H index entries rearranged %H %H Revision 3.19 1993/05/25 08:46:57 fceller %H added 'IsIdentical' %H %H Revision 3.18 1993/05/04 14:55:44 fceller %H fixed description of 'Maximum' and 'Minimum' %H %H Revision 3.17 93/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.16 1993/02/18 13:38:59 felsch %H more examples fixed %H %H Revision 3.15 1993/02/12 11:37:19 felsch %H examples adjusted to line length 72 %H %H Revision 3.14 1993/02/12 11:24:21 martin %H fixed an example %H %H Revision 3.13 1993/02/10 18:03:06 martin %H added the sublist extraction and assignment %H %H Revision 3.12 1993/02/07 14:33:00 felsch %H example adjusted %H %H Revision 3.11 1993/02/03 13:12:51 felsch %H examples fixed %H %H Revision 3.10 1992/04/09 11:36:01 martin %H made a few changes so that two LaTeX passes suffice %H %H Revision 3.9 1992/04/02 20:43:40 martin %H fixed the description of 'Position' and 'PositionSorted' %H %H Revision 3.8 1992/03/25 15:19:50 martin %H reformatted the first paragraphs %H %H Revision 3.7 1992/03/25 15:18:02 martin %H changed "Words in Solvable Groups" to "Words in Finite Polycyclic Groups" %H %H Revision 3.6 1992/03/11 08:48:48 martin %H added "Identical Lists" %H %H Revision 3.5 1991/12/30 09:41:54 martin %H changed incorrect reference to "Cyclotomic Fields" %H %H Revision 3.4 1991/12/27 16:07:04 martin %H revised everything for GAP 3.1 manual %H %H Revision 3.3 1991/07/26 12:34:01 martin %H improved the index %H %H Revision 3.2 1991/07/26 09:01:07 martin %H changed |\GAP\ | to |{\GAP}| %H %H Revision 3.1 1991/07/25 16:16:59 martin %H fixed some minor typos %H %H Revision 3.0 1991/04/11 11:54:20 martin %H Initial revision under RCS. %H %% \Chapter{Lists}% \index{type!list} Lists are the most important way to collect objects and treat them together. A *list* is a collection of elements. A list also implies a partial mapping from the integers to the elements. I.e., there is a first element of a list, a second, a third, and so on. List constants are written by writing down the elements in order between square brackets '[', ']', and separating them with commas ','. An *empty list*, i.e., a list with no elements, is written as '[]'. | gap> [ 1, 2, 3 ]; [ 1, 2, 3 ] # a list with three elements gap> [ [], [ 1 ], [ 1, 2 ] ]; [ [ ], [ 1 ], [ 1, 2 ] ] # a list may contain other lists | Usually a list has no holes, i.e., contain an element at every position. However, it is absolutely legal to have lists with holes. They are created by leaving the entry between the commas empty. Lists with holes are sometimes convenient when the list represents a mapping from a finite, but not consecutive, subset of the positive integers. We say that a list that has no holes is *dense*. | gap> l := [ , 4, 9,, 25,, 49,,,, 121 ];; gap> l[3]; 9 gap> l[4]; Error, List Element: [4] must have a value | It is most common that a list contains only elements of one type. This is not a must though. It is absolutely possible to have lists whose elements are of different types. We say that a list whose elements are all of the same type is *homogeneous*. | gap> l := [ 1, E(2), Z(3), (1,2,3), [1,2,3], "What a mess" ];; gap> l[1]; l[3]; l[5][2]; 1 Z(3) 2 | The first sections describe the functions that test if an object is a list and convert an object to a list (see "IsList" and "List"). The next section describes how one can access elements of a list (see "List Elements" and "Length"). The next sections describe how one can change lists (see "List Assignment", "Add", "Append", "Identical Lists", "Enlarging Lists"). The next sections describe the operations applicable to lists (see "Comparisons of Lists" and "Operations for Lists"). The next sections describe how one can find elements in a list (see "In", "Position", "PositionSorted", "PositionProperty"). The next sections describe the functions that construct new lists, e.g., sublists (see "Concatenation", "Flat", "Reversed", "Sublist", "Cartesian"). The next sections describe the functions deal with the subset of elements of a list that have a certain property (see "Number", "Collected", "Filtered", "ForAll", "ForAny", "First"). The next sections describe the functions that sort lists (see "Sort", "SortParallel", "Sortex", "Permuted"). The next sections describe the functions to compute the product, sum, maximum, and minimum of the elements in a list (see "Product", "Sum", "Maximum", "Minimum", "Iterated"). The final section describes the function that takes a random element from a list (see "RandomList"). Lists are also used to represent sets, subsets, vectors, and ranges (see "Sets", "Boolean Lists", "Vectors", and "Ranges"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsList}% \index{test!for a list} 'IsList( )' 'IsList' returns 'true' if the argument , which can be an arbitrary object, is a list and 'false' otherwise. Will signal an error if is an unbound variable. | gap> IsList( [ 1, 3, 5, 7 ] ); true gap> IsList( 1 ); false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{List}% \index{convert!to a list}% \index{map} 'List( )' \\ 'List( , )' In its first form 'List' returns the argument , which must be a list, a permutation, a string or a word, converted into a list. If is a list, it is simply returned. If is a permutation, 'List' returns a list where the -th element is the image of under the permutation . If is a word, 'List' returns a list where the -th element is the -th generator of the word, as a word of length 1. | gap> List( [1,2,3] ); [ 1, 2, 3 ] gap> List( (1,2)(3,4,5) ); [ 2, 1, 4, 5, 3 ] | In its second form 'List' returns a new list, where each element is the result of applying the function , which must take exactly one argument and handle the elements of , to the corresponding element of the list . The list must not contain holes. | gap> List( [1,2,3], x->x^2 ); [ 1, 4, 9 ] gap> List( [1..10], IsPrime ); [ false, true, true, false, true, false, true, false, false, false ]| Note that this function is called 'map' in Lisp and many other similar programming languages. This name violates the {\GAP} rule that verbs are used for functions that change their arguments. According to this rule 'map' would change , replacing every element with the result of the application to this argument. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{List Elements}% \index{accessing!list elements} '[ ]' The above construct evaluates to the -th element of the list . must be a positive integer. List indexing is done with origin 1, i.e., the first element of the list is the element at position 1. | gap> l := [ 2, 3, 5, 7, 11, 13 ];; gap> l[1]; 2 gap> l[2]; 3 gap> l[6]; 13 | If does not evaluate to a list, or does not evaluate to a positive integer, or '[]' is unbound an error is signalled. As usual you can leave the break loop (see "Break Loops") with 'quit;'. On the other hand you can return a result to be used in place of the list element by 'return ;'. '\{ \}' The above construct evaluates to a new list whose first element is '[[1]]', whose second element is '[[2]]', and so on. must be a dense list of positive integers, it need, however, not be sorted and may contain duplicate elements. If for any , '[ [] ]' is unbound, an error is signalled. | gap> l := [ 2, 3, 5, 7, 11, 13, 17, 19 ];; gap> l{[4..6]}; [ 7, 11, 13 ] gap> l{[1,7,1,8]}; [ 2, 17, 2, 19 ] | The result is a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the left operand (see "Identical Lists"). It is possible to nest such sublist extractions, as can be seen in the following example. | gap> m := [ [1,2,3], [4,5,6], [7,8,9], [10,11,12] ];; gap> m{[1,2,3]}{[3,2]}; [ [ 3, 2 ], [ 6, 5 ], [ 9, 8 ] ] gap> l := m{[1,2,3]};; l{[3,2]}; [ [ 7, 8, 9 ], [ 4, 5, 6 ] ] | Note the difference between the two examples. The latter extracts elements 1, 2, and 3 from and then extracts the elements 3 and 2 from *this list*. The former extracts elements 1, 2, and 3 from and then extracts the elements 3 and 2 from *each of those element lists*. To be precise. With each selector '[]' or '\{\}' we associate a *level* that is defined as the number of selectors of the form '\{\}' to its left in the same expression. For example | l[pos1]{poss2}{poss3}[pos4]{poss5}[pos6] level 0 0 1 1 1 2 | Then a selector '[]' of level is computed as 'ListElement(,,)', where 'ListElement' is defined as follows | ListElement := function ( list, pos, level ) if level = 0 then return list[pos]; else return List( list, elm -> ListElement(elm,pos,level-1) ); fi; end; | and a selector '\{\}' of level is computed as 'ListElements(,,)', where 'ListElements' is defined as follows | ListElements := function ( list, poss, level ) if level = 0 then return list{poss}; else return List( list, elm -> ListElements(elm,poss,level-1) ); fi; end; | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Length}% \index{length!of a list} 'Length( )' 'Length' returns the length of the list . The *length* is defined as 0 for the empty list, and as the largest positive integer such that '[]' has an assigned value for nonempty lists. Note that the length of a list may change if new elements are added to it or assigned to previously unassigned positions. | gap> Length( [] ); 0 gap> Length( [ 2, 3, 5, 7, 11, 13, 17, 19 ] ); 8 gap> Length( [ 1, 2,,, 5 ] ); 5 | For lists that contain no holes 'Length', 'Number' (see "Number"), and 'Size' (see "Size") return the same value. For lists with holes 'Length' returns the largest index of a bound entry, 'Number' returns the number of bound entries, and 'Size' signals an error. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{List Assignment}% \index{assignment!to a list} '[ ] \:= ;' The list assignment assigns the object , which can be of any type, to the list entry at the position , which must be a positive integer, in the list . That means that accessing the -th element of the list will return after this assignment. | gap> l := [ 1, 2, 3 ];; gap> l[1] := 3;; l; # assign a new object [ 3, 2, 3 ] gap> l[2] := [ 4, 5, 6 ];; l; # may be of any type [ 3, [ 4, 5, 6 ], 3 ] gap> l[ l[1] ] := 10;; l; # may be an expression [ 3, [ 4, 5, 6 ], 10 ] | If the index is larger than the length of the list (see "Length"), the list is automatically enlarged to make room for the new element. Note that it is possible to generate lists with holes that way. | gap> l[4] := "another entry";; l; # is enlarged [ 3, [ 4, 5, 6 ], 10, "another entry" ] gap> l[ 10 ] := 1;; l; # now has a hole [ 3, [ 4, 5, 6 ], 10, "another entry",,,,,, 1 ] | The function 'Add' (see "Add") should be used if you want to add an element to the end of the list. Note that assigning to a list changes the list. The ability to change an object is only available for lists and records (see "Identical Lists"). If does not evaluate to a list, does not evaluate to a positive integer or is a call to a function which does not return a value, for example 'Print' (see "Print"), an error is signalled As usual you can leave the break loop (see "Break Loops") with 'quit;'. On the other hand you can continue the assignment by returning a list, an index or an object using 'return ;'. '\{ \} \:= ;' The list assignment assigns the object '[1]', which can be of any type, to the list at the position '[1]', the object '[2]' to '[[2]]', and so on. must be a dense list of positive integers, it need, however, not be sorted and may contain duplicate elements. must be a dense list and must have the same length as . | gap> l := [ 2, 3, 5, 7, 11, 13, 17, 19 ];; gap> l{[1..4]} := [10..13];; l; [ 10, 11, 12, 13, 11, 13, 17, 19 ] gap> l{[1,7,1,10]} := [ 1, 2, 3, 4 ];; l; [ 3, 11, 12, 13, 11, 13, 2, 19,, 4 ] | It is possible to nest such sublist assignments, as can be seen in the following example. | gap> m := [ [1,2,3], [4,5,6], [7,8,9], [10,11,12] ];; gap> m{[1,2,3]}{[3,2]} := [ [11,12], [13,14], [15,16] ];; m; [ [ 1, 12, 11 ], [ 4, 14, 13 ], [ 7, 16, 15 ], [ 10, 11, 12 ] ] | The exact behaviour is defined in the same way as for list extractions (see "List Elements"). Namely with each selector '[]' or '\{\}' we associate a *level* that is defined as the number of selectors of the form '\{\}' to its left in the same expression. For example | l[pos1]{poss2}{poss3}[pos4]{poss5}[pos6] level 0 0 1 1 1 2 | Then a list assignment '[] \:= ;' of level is computed as 'ListAssignment( , , , )', where 'ListAssignment' is defined as follows | ListAssignment := function ( list, pos, vals, level ) local i; if level = 0 then list[pos] := vals; else for i in [1..Length(list)] do ListAssignment( list[i], pos, vals[i], level-1 ); od; fi; end; | and a list assignment '\{\} \:= ' of level is computed as 'ListAssignments( , , , )', where 'ListAssignments' is defined as follows | ListAssignments := function ( list, poss, vals, level ) local i; if level = 0 then list{poss} := vals; else for i in [1..Length(list)] do ListAssignments( list[i], poss, vals[i], level-1 ); od; fi; end; | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Add}% \index{add!an element to a list} 'Add( , )' 'Add' adds the element to the end of the list , i.e., it is equivalent to the assignment '[ Length() + 1 ] \:= '. The list is automatically enlarged to make room for the new element. 'Add' returns nothing, it is called only for its side effect. Note that adding to a list changes the list. The ability to change an object is only available for lists and records (see "Identical Lists"). To add more than one element to a list use 'Append' (see "Append"). | gap> l := [ 2, 3, 5 ];; Add( l, 7 ); l; [ 2, 3, 5, 7 ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Append}% \index{add!elements to a list}% \index{append!elements to a list} 'Append( , )' 'Append' adds (see "Add") the elements of the list to the end of the list . may contain holes, in which case the corresponding entries in will be left unbound. 'Append' returns nothing, it is called only for its side effect. | gap> l := [ 2, 3, 5 ];; Append( l, [ 7, 11, 13 ] ); l; [ 2, 3, 5, 7, 11, 13 ] gap> Append( l, [ 17,, 23 ] ); l; [ 2, 3, 5, 7, 11, 13, 17,, 23 ] | Note that appending to a list changes the list. The ability to change an object is only available for lists and records (see "Identical Lists"). Note that 'Append' changes the first argument, while 'Concatenation' (see "Concatenation") creates a new list and leaves its arguments unchanged. As usual the name of the function that work destructively is a verb, but the name of the function that creates a new object is a substantive. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Identical Lists} With the list assignment (see "List Assignment", "Add", "Append") it is possible to change a list. The ability to change an object is only available for lists and records. This section describes the semantic consequences of this fact. You may think that in the following example the second assignment changes the integer, and that therefore the above sentence, which claimed that only lists and records can be changed is wrong | i := 3; i := i + 1;| But in this example not the *integer* '3' is changed by adding one to it. Instead the *variable* 'i' is changed by assigning the value of 'i+1', which happens to be '4', to 'i'. The same thing happens in the following example | l := [ 1, 2 ]; l := [ 1, 2, 3 ];| The second assignment does not change the first list, instead it assigns a new list to the variable 'l'. On the other hand, in the following example the list is changed by the second assignment. | l := [ 1, 2 ]; l[3] := 3;| To understand the difference first think of a variable as a name for an object. The important point is that a list can have several names at the same time. An assignment ' \:= ;' means in this interpretation that is a name for the object . At the end of the following example 'l2' still has the value '[ 1, 2 ]' as this list has not been changed and nothing else has been assigned to it. | l1 := [ 1, 2 ]; l2 := l1; l1 := [ 1, 2, 3 ]; | But after the following example the list for which 'l2' is a name has been changed and thus the value of 'l2' is now '[ 1, 2, 3 ]'. | l1 := [ 1, 2 ]; l2 := l1; l1[3] := 3;| We shall say that two lists are *identical* if changing one of them by a list assignment also changes the other one. This is slightly incorrect, because if *two* lists are identical, there are actually only two names for *one* list. However, the correct usage would be very awkward and would only add to the confusion. Note that two identical lists must be equal, because there is only one list with two different names. Thus identity is an equivalence relation that is a refinement of equality. Let us now consider under which circumstances two lists are identical. If you enter a list literal than the list denoted by this literal is a new list that is not identical to any other list. Thus in the following example 'l1' and 'l2' are not identical, though they are equal of course. | l1 := [ 1, 2 ]; l2 := [ 1, 2 ];| Also in the following example, no lists in the list 'l' are identical. | l := []; for i in [1..10] do l[i] := [ 1, 2 ]; od;| If you assign a list to a variable no new list is created. Thus the list value of the variable on the left hand side and the list on the right hand side of the assignment are identical. So in the following example 'l1' and 'l2' are identical lists. | l1 := [ 1, 2 ]; l2 := l1;| If you pass a list as argument, the old list and the argument of the function are identical. Also if you return a list from a function, the old list and the value of the function call are identical. So in the following example 'l1' and 'l2' are identical list | l1 := [ 1, 2 ]; f := function ( l ) return l; end; l2 := f( l1 ); | The functions 'Copy' and 'ShallowCopy' (see "Copy" and "ShallowCopy") accept a list and return a new list that is equal to the old list but that is *not* identical to the old list. The difference between 'Copy' and 'ShallowCopy' is that in the case of 'ShallowCopy' the corresponding elements of the new and the old lists will be identical, whereas in the case of 'Copy' they will only be equal. So in the following example 'l1' and 'l2' are not identical lists. | l1 := [ 1, 2 ]; l2 := Copy( l1 );| If you change a list it keeps its identity. Thus if two lists are identical and you change one of them, you also change the other, and they are still identical afterwards. On the other hand, two lists that are not identical will never become identical if you change one of them. So in the following example both 'l1' and 'l2' are changed, and are still identical. | l1 := [ 1, 2 ]; l2 := l1; l1[1] := 2;| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsIdentical} 'IsIdentical( , )' 'IsIdentical' returns 'true' if the objects and are identical. Unchangeable objects are considered identical if the are equal. Changeable objects, i.e., lists and records, are identical if changing one of them by an assignment also changes the other one, as described in "Identical Lists". | gap> IsIdentical( 1, 1 ); true gap> IsIdentical( 1, () ); false gap> l := [ 'h', 'a', 'l', 'l', 'o' ];; gap> l = "hallo"; true gap> IsIdentical( l, "hallo" ); false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Enlarging Lists} The previous section (see "List Assignment") told you (among other things), that it is possible to assign beyond the logical end of a list, automatically enlarging the list. This section tells you how this is done. It would be extremly wasteful to make all lists large enough so that there is room for all assignments, because some lists may have more than 100000 elements, while most lists have less than 10 elements. On the other hand suppose every assignment beyond the end of a list would be done by allocating new space for the list and copying all entries to the new space. Then creating a list of 1000 elements by assigning them in order, would take half a million copy operations and also create a lot of garbage that the garbage collector would have to reclaim. So the following strategy is used. If a list is created it is created with exactly the correct size. If a list is enlarged, because of an assignment beyond the end of the list, it is enlarged by at least '/8 + 4' entries. Therefore the next assignments beyond the end of the list do not need to enlarge the list. For example creating a list of 1000 elements by assigning them in order, would now take only 32 enlargements. The result of this is of course that the *physical length*, which is also called the size, of a list may be different from the *logical length*, which is usually called simply the length of the list. Aside from the implications for the performance you need not be aware of the physical length. In fact all you can ever observe, for example by calling 'Length' is the logical length. Suppose that 'Length' would have to take the physical length and then test how many entries at the end of a list are unassigned, to compute the logical length of the list. That would take too much time. In order to make 'Length', and other functions that need to know the logical length, more efficient, the length of a list is stored along with the list. A note aside. In the previous version 2.4 of {\GAP} a list was indeed enlarged every time an assignment beyond the end of the list was performed. To deal with the above inefficiency the following hacks where used. Instead of creating lists in order they were usually created in reverse order. In situations where this was not possible a dummy assignment to the last position was performed, for example | l := []; l[1000] := "dummy"; l[1] := first_value(); for i from 2 to 1000 do l[i] := next_value(l[i-1]); od; | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Comparisons of Lists}% \index{comparisons!of lists} ' = ' \\ ' \<> ' The equality operator '=' evaluates to 'true' if the two lists and are equal and 'false' otherwise. The inequality operator '\<>' evaluates to 'true' if the two lists are not equal and 'false' otherwise. Two lists and are equal if and only if for every index , either both entries '[]' and '[]' are unbound, or both are bound and are equal, i.e., '[] = []' is 'true'. | gap> [ 1, 2, 3 ] = [ 1, 2, 3 ]; true gap> [ , 2, 3 ] = [ 1, 2, ]; false gap> [ 1, 2, 3 ] = [ 3, 2, 1 ]; false | ' \<\ ', ' \<= ' ' > ', ' >= ' The operators '\<', '\<=', '>' and '>=' evaluate to 'true' if the list is less than, less than or equal to, greater than, or greater than or equal to the list and to 'false' otherwise. Lists are ordered lexicographically, with unbound entries comparing very small. That means the following. Let be the smallest positive integer , such that neither both entries '[]' and '[]' are unbound, nor both are bound and equal. Then is less than if either '[]' is unbound (and '[]' is not) or both are bound and '[] \<\ []' is 'true'. | gap> [ 1, 2, 3, 4 ] < [ 1, 2, 4, 8 ]; true # '[3] \<\ [3]' gap> [ 1, 2, 3 ] < [ 1, 2, 3, 4 ]; true # '[4]' is unbound and therefore very small gap> [ 1, , 3, 4 ] < [ 1, 2, 3 ]; true # '[2]' is unbound and therefore very small | You can also compare objects of other types, for example integers or permutations with lists. Of course those objects are never equal to a list. Records (see "Records") are greater than lists, objects of every other type are smaller than lists. | gap> 123 < [ 1, 2, 3 ]; true gap> [ 1, 2, 3 ] < rec( a := 123 ); true | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Lists}% \index{operations!for lists} ' \*\ '\\ ' \*\ ' The operator '\*' evaluates to the product of list by an object . The product is a new list that at each position contains the product of the corresponding element of by . may contain holes, in which case the result will contain holes at the same positions. The elements of and must be objects of the following types; integers (see "Integers"), rationals (see "Rationals"), cyclotomics (see "Cyclotomics"), elements of a finite field (see "Finite Fields"), permutations (see "Permutations"), matrices (see "Matrices"), words in abstract generators (see "Words in Abstract Generators"), or words in solvable groups (see "Words in Finite Polycyclic Groups"). | gap> [ 1, 2, 3 ] * 2; [ 2, 4, 6 ] gap> 2 * [ 2, 3,, 5,, 7 ]; [ 4, 6,, 10,, 14 ] gap> [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ] * (1,4); [ (1,4), (1,4)(2,3), (1,2,4), (1,2,3,4), (1,3,2,4), (1,3,4) ] | Many more operators are available for vectors and matrices, which are also represented by lists (see "Operations for Vectors", "Operations for Matrices"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{In}% \index{test!for membership} ' in ' The 'in' operator evaluates to 'true' if the object is an element of the list and to 'false' otherwise. is an element of if there is a positive integer such that '[]=' is 'true'. may be an object of an arbitrary type and may be a list containing elements of any type. It is much faster to test for membership for sets, because for sets, which are always sorted (see "Sets"), 'in' can use a binary search, instead of the linear search used for ordinary lists. So if you have a list for which you want to perform a large number of membership tests you may consider converting it to a set with the function 'Set' (see "Set"). | gap> 1 in [ 2, 2, 1, 3 ]; true gap> 1 in [ 4, -1, 0, 3 ]; false gap> s := Set([2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32]);; gap> 17 in s; false # uses binary search and only 4 comparisons gap> 1 in [ "This", "is", "a", "list", "of", "strings" ]; false gap> [1,2] in [ [0,6], [0,4], [1,3], [1,5], [1,2], [3,4] ]; true | 'Position' (see "Position") and 'PositionSorted' (see "PositionSorted") allow you to find the position of an element in a list. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Position}% \index{find!an element in a list} 'Position( , )' 'Position' returns the position of the element , which may be an object of any type, in the list . If the element is not in the list the result is 'false'. If the element appears several times, the first position is returned. It is much faster to search for an element in a set, because for sets, which are always sorted (see "Sets"), 'Position' can use a binary search, instead of the linear search used for ordinary lists. So if you have a list for which you want to perform a large number of searches you may consider converting it to a set with the function 'Set' (see "Set"). | gap> Position( [ 2, 2, 1, 3 ], 1 ); 3 gap> Position( [ 2, 1, 1, 3 ], 1 ); 2 gap> Position( [ 4, -1, 0, 3 ], 1 ); false gap> s := Set([2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32]);; gap> Position( s, 17 ); false # uses binary search and only 4 comparisons gap> Position( [ "This", "is", "a", "list", "of", "strings" ], 1 ); false gap> Position( [ [0,6], [0,4], [1,3], [1,5], [1,2], [3,4] ], [1,2] ); 5 | The 'in' operator (see "In") can be used if you are only interested to know whether the element is in the list or not. 'PositionSorted' (see "PositionSorted") can be used if the list is sorted. 'PositionProperty' (see "PositionProperty") allows you to find the position of an element that satisfies a certain property in a list. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PositionSorted}% \index{find!an element in a sorted list} 'PositionSorted( , )' \\ 'PositionSorted( , , )' In the first form 'PositionSorted' returns the position of the element , which may be an object of any type, with respect to the sorted list . In the second form 'PositionSorted' returns the position of the element , which may be an object of any type with respect to the list , which must be sorted with respect to . must be a function of two arguments that returns 'true' if the first argument is less than the second argument and 'false' otherwise. 'PositionSorted' returns such that '[-1] \< ' and ' \<= []'. That means, if appears once in , its position is returned. If appears several times in , the position of the first occurrence is returned. If is not an element of , the index where must be inserted to keep the list sorted is returned. | gap> PositionSorted( [1,4,5,5,6,7], 0 ); 1 gap> PositionSorted( [1,4,5,5,6,7], 2 ); 2 gap> PositionSorted( [1,4,5,5,6,7], 4 ); 2 gap> PositionSorted( [1,4,5,5,6,7], 5 ); 3 gap> PositionSorted( [1,4,5,5,6,7], 8 ); 7 | 'Position' (see "Position") is another function that returns the position of an element in a list. 'Position' accepts unsorted lists, uses linear instead of binary search and returns 'false' if is not in . %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PositionProperty} 'PositionProperty( , )' 'PositionProperty' returns the position of the first element in the list for which the unary function returns 'true'. must not contain holes. If returns 'false' for all elements of 'false' is returned. must return 'true' or 'false' for every element of , otherwise an error is signalled. | gap> PositionProperty( [10^7..10^8], IsPrime ); 20 gap> PositionProperty( [10^5..10^6], > n -> not IsPrime(n) and IsPrimePowerInt(n) ); 490 | 'First' (see "First") allows you to extract the first element of a list that satisfies a certain property. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Concatenation}% \index{concatenation!of lists} 'Concatenation( , .. )' \\ 'Concatenation( )' In the first form 'Concatenation' returns the concatenation of the lists , , etc. The *concatenation* is the list that begins with the elements of , followed by the elements of and so on. Each list may also contain holes, in which case the concatenation also contains holes at the corresponding positions. | gap> Concatenation( [ 1, 2, 3 ], [ 4, 5 ] ); [ 1, 2, 3, 4, 5 ] gap> Concatenation( [2,3,,5,,7], [11,,13,,,,17,,19] ); [ 2, 3,, 5,, 7, 11,, 13,,,, 17,, 19 ] | In the second form must be a list of lists , , etc, and 'Concatenation' returns the concatenation of those lists. | gap> Concatenation( [ [1,2,3], [2,3,4], [3,4,5] ] ); [ 1, 2, 3, 2, 3, 4, 3, 4, 5 ] | The result is a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the argument lists (see "Identical Lists"). Note that 'Concatenation' creates a new list and leaves it arguments unchanged, while 'Append' (see "Append") changes its first argument. As usual the name of the function that works destructively is a verb, but the name of the function that creates a new object is a substantive. 'Set(Concatenation(,..))' (see "Set") is a way to compute the union of sets, however, 'Union' (see "Union") is more efficient. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Flat} 'Flat( )' 'Flat' returns the list of all elements that are contained in the list or its sublists. That is, 'Flat' first makes a new empty list . Then it loops over the elements of . If is not a list it is added to , otherwise 'Flat' appends 'Flat( )' to . | gap> Flat( [ 1, [ 2, 3 ], [ [ 1, 2 ], 3 ] ] ); [ 1, 2, 3, 1, 2, 3 ] gap> Flat( [ ] ); [ ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Reversed}% \index{reverse the elements of a list} 'Reversed( )' 'Reversed' returns a new list that contains the elements of the list , which must not contain holes, in reverse order. The argument list is unchanged. | gap> Reversed( [ 1, 4, 5, 5, 6, 7 ] ); [ 7, 6, 5, 5, 4, 1 ] | The result is a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the argument list (see "Identical Lists"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Sublist} 'Sublist( , )' 'Sublist' returns a new list in which the -th element is the element '[ [ ] ]', of the list . must be a list of positive integers without holes, it need, however, not be sorted and may contains duplicate elements. If '[ [ ] ]' is unbound for an , an error is signalled. | gap> Sublist( [ 2, 3, 5, 7, 11, 13, 17, 19 ], [4..6] ); [ 7, 11, 13 ] gap> Sublist( [ 2, 3, 5, 7, 11, 13, 17, 19 ], [1,7,1,8] ); [ 2, 17, 2, 19 ] | The result is a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the argument list (see "Identical Lists"). 'Filtered' (see "Filtered") allows you to extract elements from a list according to a predicate. 'Sublist' has been made obsolete by the introduction of the construct '\{ \}' (see "List Elements"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Cartesian}% \index{cross product of lists} 'Cartesian( , .. )' \\ 'Cartesian( )' In the first form 'Cartesian' returns the cartesian product of the lists , , etc. In the second form must be a list of lists , , etc., and 'Cartesian' returns the cartesian product of those lists. The *cartesian product* is a list of lists , such that the first element of is an element of , the second element of is an element of , and so on. The total number of elements in is the product of the lengths of the argument lists. In particular is empty if and only if at least one of the argument lists is empty. Also contains duplicates if and only if no argument list is empty and at least one contains duplicates. The last index runs fastest. That means that the first element of contains the first element from , from and so on. The second element of contains the first element from , the first from , an so on, but the last element of is the second element of the last argument list. This implies that is a set if and only if all argument lists are sets. | gap> Cartesian( [1,2], [3,4], [5,6] ); [ [ 1, 3, 5 ], [ 1, 3, 6 ], [ 1, 4, 5 ], [ 1, 4, 6 ], [ 2, 3, 5 ], [ 2, 3, 6 ], [ 2, 4, 5 ], [ 2, 4, 6 ] ] gap> Cartesian( [1,2,2], [1,1,2] ); [ [ 1, 1 ], [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 1 ], [ 2, 2 ], [ 2, 1 ], [ 2, 1 ], [ 2, 2 ] ] | The function 'Tuples' (see "Tuples") computes the -fold cartesian product of a list. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Number}% \index{number!of elements in a list} 'Number( )' \\ 'Number( , )' In the first form 'Number' returns the number of bound entries in the list . For lists that contain no holes 'Number', 'Length' (see "Length"), and 'Size' (see "Size") return the same value. For lists with holes 'Number' returns the number of bound entries, 'Length' returns the largest index of a bound entry, and 'Size' signals an error. 'Number' returns the number of elements of the list for which the unary function returns 'true'. If an element for which returns 'true' appears several times in it will also be counted several times. must return either 'true' or 'false' for every element of , otherwise an error is signalled. | gap> Number( [ 2, 3, 5, 7 ] ); 4 gap> Number( [, 2, 3,, 5,, 7,,,, 11 ] ); 5 gap> Number( [1..20], IsPrime ); 8 gap> Number( [ 1, 3, 4, -4, 4, 7, 10, 6 ], IsPrimePowerInt ); 4 gap> Number( [ 1, 3, 4, -4, 4, 7, 10, 6 ], > n -> IsPrimePowerInt(n) and n mod 2 <> 0 ); 2 | 'Filtered' (see "Filtered") allows you to extract the elements of a list that have a certain property. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Collected} 'Collected( )' 'Collected' returns a new list that contains for each different element of a list of two elements, the first element is itself, and the second element is the number of times appears in . The order of those pairs in corresponds to the ordering of the elements , so that the result is sorted. | gap> Factors( Factorial( 10 ) ); [ 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7 ] gap> Collected( last ); [ [ 2, 8 ], [ 3, 4 ], [ 5, 2 ], [ 7, 1 ] ] gap> Collected( last ); [ [ [ 2, 8 ], 1 ], [ [ 3, 4 ], 1 ], [ [ 5, 2 ], 1 ], [ [ 7, 1 ], 1 ] ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Filtered} 'Filtered( , )' 'Filtered' returns a new list that contains those elements of the list for which the unary function returns 'true'. The order of the elements in the result is the same as the order of the corresponding elements of . If an element, for which returns 'true' appears several times in it will also appear the same number of times in the result. may contain holes, they are ignored by 'Filtered'. must return either 'true' or 'false' for every element of , otherwise an error is signalled. | gap> Filtered( [1..20], IsPrime ); [ 2, 3, 5, 7, 11, 13, 17, 19 ] gap> Filtered( [ 1, 3, 4, -4, 4, 7, 10, 6 ], IsPrimePowerInt ); [ 3, 4, 4, 7 ] gap> Filtered( [ 1, 3, 4, -4, 4, 7, 10, 6 ], > n -> IsPrimePowerInt(n) and n mod 2 <> 0 ); [ 3, 7 ] | The result is a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the argument list (see "Identical Lists"). 'Sublist' (see "Sublist") allows you to extract elements of a list according to indices given in another list. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ForAll} 'ForAll( , )' 'ForAll' returns 'true' if the unary function returns 'true' for all elements of the list and 'false' otherwise. may contain holes. must return either 'true' or 'false' for every element of , otherwise an error is signalled. | gap> ForAll( [1..20], IsPrime ); false gap> ForAll( [2,3,4,5,8,9], IsPrimePowerInt ); true gap> ForAll( [2..14], n -> IsPrimePowerInt(n) or n mod 2 = 0 ); true | 'ForAny' (see "ForAny") allows you to test if any element of a list satisfies a certain property. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ForAny} 'ForAny( , )' 'ForAny' returns 'true' if the unary function returns 'true' for at least one element of the list and 'false' otherwise. may contain holes. must return either 'true' or 'false' for every element of , otherwise 'ForAny' signals an error. | gap> ForAny( [1..20], IsPrime ); true gap> ForAny( [2,3,4,5,8,9], IsPrimePowerInt ); true gap> ForAny( [2..14], > n -> IsPrimePowerInt(n) and n mod 5 = 0 and not IsPrime(n) ); false | 'ForAll' (see "ForAll") allows you to test if all elements of a list satisfies a certain propertie. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{First} 'First( , )' 'First' returns the first element of the list for which the unary function returns 'true'. may contain holes. must return either 'true' or 'false' for every element of , otherwise an error is signalled. If returns 'false' for every element of an error is signalled. | gap> First( [10^7..10^8], IsPrime ); 10000019 gap> First( [10^5..10^6], > n -> not IsPrime(n) and IsPrimePowerInt(n) ); 100489 | 'PositionProperty' (see "PositionProperty") allows you to find the position of the first element in a list that satisfies a certain property. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Sort}% \index{sort a list} 'Sort( )' \\ 'Sort( , )' 'Sort' sorts the list in increasing order, using shellsort. In the first form 'Sort' uses the operator '\<' to compare the elements. In the second form 'Sort' uses the function to compare elements. This function must be a function taking two arguments that returns 'true' if the first is strictly smaller than the second and 'false' otherwise. 'Sort' does not return anything, since it changes the argument . Use 'ShallowCopy' (see "ShallowCopy") if you want to keep . Use 'Reversed' (see "Reversed") if you want to get a new list sorted in decreasing order. It is possible to sort lists that contain multiple elements which compare equal. It is not guaranteed that those elements keep their relative order, i.e., 'Sort' is not stable. | gap> list := [ 5, 4, 6, 1, 7, 5 ];; Sort( list ); list; [ 1, 4, 5, 5, 6, 7 ] gap> list := [ [0,6], [1,2], [1,3], [1,5], [0,4], [3,4] ];; gap> Sort( list, function(v,w) return v*v < w*w; end ); list; [ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 3, 4 ], [ 1, 5 ], [ 0, 6 ] ] # sorted according to the Euclidian distance from [0,0] gap> list := [ [0,6], [1,3], [3,4], [1,5], [1,2], [0,4], ];; gap> Sort( list, function(v,w) return v[1] < w[1]; end ); list; [ [ 0, 6 ], [ 0, 4 ], [ 1, 3 ], [ 1, 5 ], [ 1, 2 ], [ 3, 4 ] ] # note the random order of the elements with equal first component | 'SortParallel' (see "SortParallel") allows you to sort a list and apply the exchanges that are necessary to another list in parallel. 'Sortex' (see "Sortex") sorts a list and returns the sorting permutation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SortParallel} 'SortParallel( , )' \\ 'SortParallel( , , )' 'SortParallel' sorts the list in increasing order just as 'Sort' (see "Sort") does. In parallel it applies the same exchanges that are necessary to sort to the list , which must of course have at least as many elements as does. | gap> list1 := [ 5, 4, 6, 1, 7, 5 ];; gap> list2 := [ 2, 3, 5, 7, 8, 9 ];; gap> SortParallel( list1, list2 ); gap> list1; [ 1, 4, 5, 5, 6, 7 ] gap> list2; [ 7, 3, 2, 9, 5, 8 ] # '[ 7, 3, 9, 2, 5, 8 ]' is also possible | 'Sortex' (see "Sortex") sorts a list and returns the sorting permutation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Sortex} 'Sortex( )' 'Sortex' sorts the list and returns the permutation that must be applied to to obtain the sorted list. | gap> list1 := [ 5, 4, 6, 1, 7, 5 ];; gap> list2 := Copy( list1 );; gap> perm := Sortex( list1 ); (1,3,5,6,4) gap> list1; [ 1, 4, 5, 5, 6, 7 ] gap> Permuted( list2, perm ); [ 1, 4, 5, 5, 6, 7 ] | 'Permuted' (see "Permuted") allows you to rearrange a list according to a given permutation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Permuted} 'Permuted( , )' 'Permuted' returns a new list that contains the elements of the list permuted according to the permutation . That is '[\^] = []'. | gap> Permuted( [ 5, 4, 6, 1, 7, 5 ], (1,3,5,6,4) ); [ 1, 4, 5, 5, 6, 7 ] | 'Sortex' (see "Sortex") allows you to compute the permutation that must be applied to a list to get the sorted list. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Product}% \index{multiply!the elements of a list} 'Product( )' \\ 'Product( , )' In the first form 'Product' returns the product of the elements of the list , which must have no holes. If is empty, the integer 1 is returned. In the second form 'Product' applies the function to each element of the list , which must have no holes, and multiplies the results. If the is empty, the integer 1 is returned. | gap> Product( [ 2, 3, 5, 7, 11, 13, 17, 19 ] ); 9699690 gap> Product( [1..10], x->x^2 ); 13168189440000 gap> Product( [ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) ] ); (1,4)(2,3) | 'Sum' (see "Sum") computes the sum of the elements of a list. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Sum}% \index{add!the elements of a list} 'Sum( )' \\ 'Sum( , )' In the first form 'Sum' returns the sum of the elements of the list , which must have no holes. If is empty 0 is returned. In the second form 'Sum' applies the function to each element of the list , which must have no holes, and sums the results. If the is empty 0 is returned. | gap> Sum( [ 2, 3, 5, 7, 11, 13, 17, 19 ] ); 77 gap> Sum( [1..10], x->x^2 ); 385 gap> Sum( [ [1,2], [3,4], [5,6] ] ); [ 9, 12 ] | 'Product' (see "Product") computes the product of the elements of a list. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Maximum}% \index{maximum!of integers}% \index{maximum!of a list} 'Maximum( , .. )' \\ 'Maximum( )' 'Maximum' returns the maximum of its arguments, i.e., that argument $obj_i$ for which $obj_k \<= obj_i$ for all $k$. In its second form 'Maximum' takes a list and returns the maximum of the elements of this list. Typically the arguments or elements of the list respectively will be integers, but actually they can be objects of an arbitrary type. This works because any two objects can be compared using the '\<' operator. | gap> Maximum( -123, 700, 123, 0, -1000 ); 700 gap> Maximum( [ -123, 700, 123, 0, -1000 ] ); 700 gap> Maximum( [ 1, 2 ], [ 0, 15 ], [ 1, 5 ], [ 2, -11 ] ); [ 2, -11 ] # lists are compared elementwise | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Minimum}% \index{minimum!of integers}% \index{minimum!of a list} 'Minimum( , .. )' \\ 'Minimum( )' 'Minimum' returns the minimum of its arguments, i.e., that argument $obj_i$ for which $obj_i \<= obj_k$ for all $k$. In its second form 'Minimum' takes a list and returns the minimum of the elements of this list. Typically the arguments or elements of the list respectively will be integers, but actually they can be objects of an arbitrary type. This works because any two objects can be compared using the '\<' operator. | gap> Minimum( -123, 700, 123, 0, -1000 ); -1000 gap> Minimum( [ -123, 700, 123, 0, -1000 ] ); -1000 gap> Minimum( [ 1, 2 ], [ 0, 15 ], [ 1, 5 ], [ 2, -11 ] ); [ 0, 15 ] # lists are compared elementwise | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Iterated}% \index{iterate a function over a list} 'Iterated( , )' 'Iterated' returns the result of the iterated application of the function , which must take two arguments, to the elements of . More precisely 'Iterated' returns the result of the following application, '(..( ( [1], [2] ), [3] ),..,[] )'. | gap> Iterated( [ 126, 66, 105 ], Gcd ); 3 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RandomList} 'RandomList( )' 'RandomList' returns a random element of the list . The results are equally distributed, i.e., all elements are equally likely to be selected. | gap> RandomList( [1..200] ); 192 gap> RandomList( [1..200] ); 152 gap> RandomList( [ [ 1, 2 ], 3, [ 4, 5 ], 6 ] ); [ 4, 5 ] | 'RandomSeed( )'% \index{RandomSeed} 'RandomSeed' seeds the pseudo random number generator 'RandomList'. Thus to reproduce a computation exactly you can call 'RandomSeed' each time before you start the computation. When {\GAP} is started the pseudo random number generator is seeded with 1. | gap> RandomSeed(1); RandomList([1..100]); RandomList([1..100]); 96 76 gap> RandomSeed(1); RandomList([1..100]); RandomList([1..100]); 96 76 | 'RandomList' is called by all random functions for domains (see "Random"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%