% This file was created automatically from coll.msk. % DO NOT EDIT! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A coll.msk GAP documentation Alexander Hulpke %% %A @(#)$Id: coll.msk,v 1.23.2.2 2006/09/16 19:02:49 jjm Exp $ %% %Y (C) 1998 School Math and Comp. Sci., University of St. Andrews, Scotland %Y Copyright (C) 2002 The GAP Group %% \Chapter{Collections} A *collection* in {\GAP} consists of elements in the same family (see~"Families"). The most important kinds of collections are *homogeneous lists* (see~"Lists") and *domains* (see~"Domains"). Note that a list is never a domain, and a domain is never a list. A list is a collection if and only if it is nonempty and homogeneous. Basic operations for collections are `Size' (see~"Size") and `Enumerator' (see~"Enumerator"); for *finite* collections, `Enumerator' admits to delegate the other operations for collections (see~"Attributes and Properties for Collections" and~"Operations for Collections") to functions for lists (see~"Lists"). Obviously, special methods depending on the arguments are needed for the computation of e.g.~the intersection of two *infinite* domains. \>IsCollection( <obj> ) C tests whether an object is a collection. Some of the functions for lists and collections have been described in the chapter about lists, mainly in Section~"Operations for Lists". In this chapter, we describe those functions for which the ``collection aspect'' seems to be more important than the ``list aspect''. As in Chapter~"Lists", an argument that is a list will be denoted by <list>, and an argument that is a collection will be denoted by <C>. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Collection Families} \>CollectionsFamily( <Fam> ) A For a family <Fam>, `CollectionsFamily' returns the family of all collections that consist of elements in <Fam>. Note that families (see~"Families") are used to describe relations between objects. Important such relations are that between an element <elm> and each collection of elements that lie in the same family as <elm>, and that between two collections whose elements lie in the same family. Therefore, all collections of elements in the family <Fam> form the new family `CollectionsFamily( <Fam> )'. \>IsCollectionFamily( <Fam> ) C is `true' if <Fam> is a family of collections, and `false' otherwise. \>ElementsFamily( <Fam> ) A returns the family from which the collections family <Fam> was created by `CollectionsFamily'. The way a collections family is created, it always has its elements family stored. If <Fam> is not a collections family (see~"IsCollectionFamily") then an error is signalled. \beginexample gap> fam:= FamilyObj( (1,2) );; gap> collfam:= CollectionsFamily( fam );; gap> fam = collfam; fam = ElementsFamily( collfam ); false true gap> collfam = FamilyObj( [ (1,2,3) ] ); collfam = FamilyObj( Group( () ) ); true true gap> collfam = CollectionsFamily( collfam ); false \endexample \>CategoryCollections( <filter> ) F Let <filter> be a filter that is `true' for all elements of a family <Fam>, by construction of <Fam>. Then `CategoryCollections' returns a category that is `true' for all elements in `CollectionsFamily( <Fam> )'. For example, the construction of `PermutationsFamily' guarantees that each of its elements lies in the filter `IsPerm', and each collection of permutations lies in the category `CategoryCollections( IsPerm )'. Note that this works only if the collections category is created *before* the collections family. So it is necessary to construct interesting collections categories immediately after the underlying category has been created. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Lists and Collections} \index{Sorted Lists as Collections} \>IsListOrCollection( <obj> ) C Several functions are defined for both lists and collections, for example `Intersection' (see~"Intersection"), `Iterator' (see~"Iterator"), and `Random' (see~"Random"). `IsListOrCollection' is a supercategory of `IsList' and `IsCollection' (that is, all lists and collections lie in this category), which is used to describe the arguments of functions such as the ones listed above. The following functions take a *list or collection* as argument, and return a corresponding *list*. They differ in whether or not the result is mutable or immutable (see~"Mutability and Copyability"), guaranteed to be sorted, or guaranteed to admit list access in constant time (see~"IsConstantTimeAccessList"). \>Enumerator( <C> ) A \>Enumerator( <list> ) A `Enumerator' returns an immutable list <enum>. If the argument is a list <list> (which may contain holes), then `Length( <enum> )' is `Length( <list> )', and <enum> contains the elements (and holes) of <list> in the same order. If the argument is a collection <C> that is not a list, then `Length( <enum> )' is the number of different elements of <C>, and <enum> contains the different elements of <C> in an unspecified order, which may change for repeated calls of `Enumerator'. `<enum>[<pos>]' may not execute in constant time (see~"IsConstantTimeAccessList"), and the size of <enum> in memory is as small as is feasible. For lists <list>, the default method is `Immutable'. For collections <C> that are not lists, there is no default method. \>EnumeratorSorted( <C> ) A \>EnumeratorSorted( <list> ) A `EnumeratorSorted' returns an immutable list <enum>. The argument must be a collection <C> or a list <list> which may contain holes but whose elements lie in the same family (see~"Families"). `Length( <enum> )' is the number of different elements of <C> resp.~<list>, and <enum> contains the different elements in sorted order, w.r.t.~`\<'. `<enum>[<pos>]' may not execute in constant time (see~"IsConstantTimeAccessList"), and the size of <enum> in memory is as small as is feasible. \beginexample gap> Enumerator( [ 1, 3,, 2 ] ); [ 1, 3,, 2 ] gap> enum:= Enumerator( Rationals );; elm:= enum[ 10^6 ]; -69/907 gap> Position( enum, elm ); 1000000 gap> IsMutable( enum ); IsSortedList( enum ); false false gap> IsConstantTimeAccessList( enum ); false gap> EnumeratorSorted( [ 1, 3,, 2 ] ); [ 1, 2, 3 ] \endexample \>EnumeratorByFunctions( <D>, <record> ) F \>EnumeratorByFunctions( <Fam>, <record> ) F `EnumeratorByFunctions' returns an immutable, dense, and duplicate-free list <enum> for which `IsBound', element access, `Length', and `Position' are computed via prescribed functions. Let <record> be a record with at least the following components. \beginitems `ElementNumber' & a function taking two arguments <enum> and <pos>, which returns `<enum>[ <pos> ]' (see~"Basic Operations for Lists"); it can be assumed that the argument <pos> is a positive integer, but <pos> may be larger than the length of <enum> (in which case an error must be signalled); note that the result must be immutable since <enum> itself is immutable, `NumberElement' & a function taking two arguments <enum> and <elm>, which returns `Position( <enum>, <elm> )' (see~"Position"); it cannot be assumed that <elm> is really contained in <enum> (and `fail' must be returned if not); note that for the three argument version of `Position', the method that is available for duplicate-free lists suffices. \enditems Further (data) components may be contained in <record> which can be used by these function. If the first argument is a domain <D> then <enum> lists the elements of <D> (in general <enum> is *not* sorted), and methods for `Length', `IsBound', and `PrintObj' may use <D>. If one wants to describe the result without creating a domain then the elements are given implicitly by the functions in <record>, and the first argument must be a family <Fam> which will become the family of <enum>; if <enum> is not homogeneous then <Fam> must be `ListsFamily', otherwise it must be the collections family of any element in <enum>. In this case, additionally the following component in <record> is needed. \beginitems `Length' & a function taking the argument <enum>, which returns the length of <enum> (see~"Length"). \enditems The following components are optional; they are used if they are present but default methods are installed for the case that they are missing. \beginitems `IsBound\\[\\]' & a function taking two arguments <enum> and <k>, which returns `IsBound( <enum>[ <k> ] )' (see~"Basic Operations for Lists"); if this component is missing then `Length' is used for computing the result, `Membership' & a function taking two arguments <elm> and <enum>, which returns `true' is <elm> is an element of <enum>, and `false' otherwise (see~"Basic Operations for Lists"); if this component is missing then `NumberElement' is used for computing the result, `AsList' & a function taking one argument <enum>, which returns a list with the property that the access to each of its elements will take roughly the same time (see~"IsConstantTimeAccessList"); if this component is missing then `ConstantTimeAccessList' is used for computing the result, `ViewObj' and `PrintObj' & two functions that print what one wants to be printed when `View( <enum> )' or `Print( <enum> )' is called (see~"View and Print"), if the `ViewObj' component is missing then the `PrintObj' method is used as a default. \enditems If the result is known to have additional properties such as being strictly sorted (see~"IsSSortedList") then it can be useful to set these properties after the construction of the enumerator, before it is used for the first time. And in the case that a new sorted enumerator of a domain is implemented via `EnumeratorByFunctions', and this construction is installed as a method for the operation `Enumerator' (see~"Enumerator"), then it should be installed also as a method for `EnumeratorSorted' (see~"EnumeratorSorted"). Note that it is *not* checked that `EnumeratorByFunctions' really returns a dense and duplicate-free list. `EnumeratorByFunctions' does *not* make a shallow copy of <record>, this record is changed in place (see~"prg:Creating Objects" in ``Programming in {\GAP}''). It would be easy to implement a slightly generalized setup for enumerators that need not be duplicate-free (where the three argument version of `Position' is supported), but the resulting overhead for the methods seems not to be justified. \){\fmark List( <C> )} \){\fmark List( <list> )} This function is described in~"List", together with the probably more frequently used version which takes a function as second argument and returns the list of function values of the list elements. \beginexample gap> l:= List( Group( (1,2,3) ) ); [ (), (1,3,2), (1,2,3) ] gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l ); true false true \endexample \>SortedList( <C> ) O \>SortedList( <list> ) O `SortedList' returns a new mutable and dense list <new>. The argument must be a collection <C> or a list <list> which may contain holes but whose elements lie in the same family (see~"Families"). `Length( <new> )' is the number of elements of <C> resp.~<list>, and <new> contains the elements in sorted order, w.r.t.~`\<='. `<new>[<pos>]' executes in constant time (see~"IsConstantTimeAccessList"), and the size of <new> in memory is proportional to its length. \beginexample gap> l:= SortedList( Group( (1,2,3) ) ); [ (), (1,2,3), (1,3,2) ] gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l ); true true true gap> SortedList( [ 1, 2, 1,, 3, 2 ] ); [ 1, 1, 2, 2, 3 ] \endexample \>SSortedList( <C> ) O \>SSortedList( <list> ) O \>Set( <C> ) O `SSortedList' (``strictly sorted list'') returns a new dense, mutable, and duplicate free list <new>. The argument must be a collection <C> or a list <list> which may contain holes but whose elements lie in the same family (see~"Families"). `Length( <new> )' is the number of different elements of <C> resp.~<list>, and <new> contains the different elements in strictly sorted order, w.r.t.~`\<'. `<new>[<pos>]' executes in constant time (see~"IsConstantTimeAccessList"), and the size of <new> in memory is proportional to its length. `Set' is simply a synonym for `SSortedList'. \beginexample gap> l:= SSortedList( Group( (1,2,3) ) ); [ (), (1,2,3), (1,3,2) ] gap> IsMutable( l ); IsSSortedList( l ); IsConstantTimeAccessList( l ); true true true gap> SSortedList( [ 1, 2, 1,, 3, 2 ] ); [ 1, 2, 3 ] \endexample \>AsList( <C> ) A \>AsList( <list> ) A `AsList' returns a immutable list <imm>. If the argument is a list <list> (which may contain holes), then `Length( <imm> )' is `Length( <list> )', and <imm> contains the elements (and holes) of <list> in the same order. If the argument is a collection <C> that is not a list, then `Length( <imm> )' is the number of different elements of <C>, and <imm> contains the different elements of <C> in an unspecified order, which may change for repeated calls of `AsList'. `<imm>[<pos>]' executes in constant time (see~"IsConstantTimeAccessList"), and the size of <imm> in memory is proportional to its length. If you expect to do many element tests in the resulting list, it might be worth to use a sorted list instead, using `AsSSortedList'. \beginexample gap> l:= AsList( [ 1, 3, 3,, 2 ] ); [ 1, 3, 3,, 2 ] gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l ); false false true gap> AsList( Group( (1,2,3), (1,2) ) ); [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ] \endexample \>AsSortedList( <C> ) A \>AsSortedList( <list> ) A `AsSortedList' returns a dense and immutable list <imm>. The argument must be a collection <C> or a list <list> which may contain holes but whose elements lie in the same family (see~"Families"). `Length( <imm> )' is the number of elements of <C> resp.~<list>, and <imm> contains the elements in sorted order, w.r.t.~`\<='. `<new>[<pos>]' executes in constant time (see~"IsConstantTimeAccessList"), and the size of <imm> in memory is proportional to its length. The only difference to the operation `SortedList' (see~"SortedList") is that `AsSortedList' returns an *immutable* list. \beginexample gap> l:= AsSortedList( [ 1, 3, 3,, 2 ] ); [ 1, 2, 3, 3 ] gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l ); false true true gap> IsSSortedList( l ); false \endexample \>AsSSortedList( <C> ) A \>AsSSortedList( <list> ) A \>AsSet( <C> ) A `AsSSortedList' (``as strictly sorted list'') returns a dense, immutable, and duplicate free list <imm>. The argument must be a collection <C> or a list <list> which may contain holes but whose elements lie in the same family (see~"Families"). `Length( <imm> )' is the number of different elements of <C> resp.~<list>, and <imm> contains the different elements in strictly sorted order, w.r.t.~`\<'. `<imm>[<pos>]' executes in constant time (see~"IsConstantTimeAccessList"), and the size of <imm> in memory is proportional to its length. Because the comparisons required for sorting can be very expensive for some kinds of objects, you should use `AsList' instead if you do not require the result to be sorted. The only difference to the operation `SSortedList' (see~"SSortedList") is that `AsSSortedList' returns an *immutable* list. `AsSet' is simply a synonym for `AsSSortedList'. In general a function that returns a set of elements is free, in fact encouraged, to return a domain instead of the proper set of its elements. This allows one to keep a given structure, and moreover the representation by a domain object is usually more space efficient. `AsSSortedList' must of course *not* do this, its only purpose is to create the proper set of elements. \index{elements!of a list or collection} \beginexample gap> l:= AsSSortedList( l ); [ 1, 2, 3 ] gap> IsMutable( l ); IsSSortedList( l ); IsConstantTimeAccessList( l ); false true true gap> AsSSortedList( Group( (1,2,3), (1,2) ) ); [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ] \endexample \>Elements( <C> ) F `Elements' does the same as `AsSSortedList' (see~"AsSSortedList"), that is, the return value is a strictly sorted list of the elements in the list or collection <C>. `Elements' is only supported for backwards compatibility. In many situations, the sortedness of the ``element list'' for a collection is in fact not needed, and one can save a lot of time by asking for a list that is *not* necessarily sorted, using `AsList' (see~"AsList"). If one is really interested in the strictly sorted list of elements in <C> then one should use `AsSet' or `AsSSortedList' instead. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Attributes and Properties for Collections} \>IsEmpty( <C> ) P \>IsEmpty( <list> ) P `IsEmpty' returns `true' if the collection <C> resp.~the list <list> is *empty* (that is it contains no elements), and `false' otherwise. \>IsFinite( <C> ) P `IsFinite' returns `true' if the collection <C> is finite, and `false' otherwise. The default method for `IsFinite' checks the size (see~"Size") of <C>. Methods for `IsFinite' may call `Size', but methods for `Size' must *not* call `IsFinite'. \index{finiteness test!for a list or collection} \>IsTrivial( <C> ) P `IsTrivial' returns `true' if the collection <C> consists of exactly one element. \>IsNonTrivial( <C> ) P `IsNonTrivial' returns `true' if the collection <C> is empty or consists of at least two elements (see~"IsTrivial"). \beginexample gap> IsEmpty( [] ); IsEmpty( [ 1 .. 100 ] ); IsEmpty( Group( (1,2,3) ) ); true false false gap> IsFinite( [ 1 .. 100 ] ); IsFinite( Integers ); true false gap> IsTrivial( Integers ); IsTrivial( Group( () ) ); false true gap> IsNonTrivial( Integers ); IsNonTrivial( Group( () ) ); true false \endexample \>IsWholeFamily( <C> ) P `IsWholeFamily' returns `true' if the collection <C> contains the whole family (see~"Families") of its elements. \beginexample gap> IsWholeFamily( Integers ) > ; # all rationals and cyclotomics lie in the family false gap> IsWholeFamily( Integers mod 3 ) > ; # all finite field elements in char. 3 lie in this family false gap> IsWholeFamily( Integers mod 4 ); true gap> IsWholeFamily( FreeGroup( 2 ) ); true \endexample \>Size( <C> ) A \>Size( <list> ) A `Size' returns the size of the collection <C>, which is either an integer or `infinity'. The argument may also be a list <list>, in which case the result is the length of <list> (see~"Length"). The default method for `Size' checks the length of an enumerator of <C>. Methods for `IsFinite' may call `Size', but methods for `Size' must not call `IsFinite'. \index{size!of a list or collection} \index{order!of a list, collection or domain} \beginexample gap> Size( [1,2,3] ); Size( Group( () ) ); Size( Integers ); 3 1 infinity \endexample \>Representative( <C> ) A `Representative' returns a *representative* of the collection <C>. Note that `Representative' is free in choosing a representative if there are several elements in <C>. It is not even guaranteed that `Representative' returns the same representative if it is called several times for one collection. The main difference between `Representative' and `Random' (see~"Random") is that `Representative' is free to choose a value that is cheap to compute, while `Random' must make an effort to randomly distribute its answers. If <C> is a domain then there are methods for `Representative' that try to fetch an element from any known generator list of <C>, see~"Domains and their Elements". Note that `Representative' does not try to *compute* generators of <C>, thus `Representative' may give up and signal an error if <C> has no generators stored at all. \index{representative!of a list or collection} \>RepresentativeSmallest( <C> ) A returns the smallest element in the collection <C>, w.r.t.~the ordering `\<'. While the operation defaults to comparing all elements, better methods are installed for some collections. \beginexample gap> Representative( Rationals ); 1 gap> Representative( [ -1, -2 .. -100 ] ); -1 gap> RepresentativeSmallest( [ -1, -2 .. -100 ] ); -100 \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Collections} \>IsSubset( <C1>, <C2> ) O `IsSubset' returns `true' if <C2>, which must be a collection, is a *subset* of <C1>, which also must be a collection, and `false' otherwise. <C2> is considered a subset of <C1> if and only if each element of <C2> is also an element of <C1>. That is `IsSubset' behaves as if implemented as `IsSubsetSet( AsSSortedList( <C1> ), AsSSortedList( <C2> ) )', except that it will also sometimes, but not always, work for infinite collections, and that it will usually work much faster than the above definition. Either argument may also be a proper set (see~"Sorted Lists and Sets"). \index{subset test!for collections} \beginexample gap> IsSubset( Rationals, Integers ); true gap> IsSubset( Integers, [ 1, 2, 3 ] ); true gap> IsSubset( Group( (1,2,3,4) ), [ (1,2,3) ] ); false \endexample \>Intersection( <C1>, <C2> ... ) F \>Intersection( <list> ) F \>Intersection2( <C1>, <C2> ) O In the first form `Intersection' returns the intersection of the collections <C1>, <C2>, etc. In the second form <list> must be a *nonempty* list of collections and `Intersection' returns the intersection of those collections. Each argument or element of <list> respectively may also be a homogeneous list that is not a proper set, in which case `Intersection' silently applies `Set' (see~"Set") to it first. The result of `Intersection' is the set of elements that lie in every of the collections <C1>, <C2>, etc. If the result is a list then it is mutable and new, i.e., not identical to any of <C1>, <C2>, etc. Methods can be installed for the operation `Intersection2' that takes only two arguments. `Intersection' calls `Intersection2'. Methods for `Intersection2' should try to maintain as much structure as possible, for example the intersection of two permutation groups is again a permutation group. \index{intersection!of collections} \beginexample gap> Intersection( CyclotomicField(9), CyclotomicField(12) ) > # this is one of the rare cases where the intersection of two infinite > ; # domains works (`CF' is a shorthand for `CyclotomicField') CF(3) gap> D12 := Group( (2,6)(3,5), (1,2)(3,6)(4,5) );; gap> Intersection( D12, Group( (1,2), (1,2,3,4,5) ) ); Group([ (1,5)(2,4) ]) gap> Intersection( D12, [ (1,3)(4,6), (1,2)(3,4) ] ) > ; # note that the second argument is not a proper set [ (1,3)(4,6) ] gap> Intersection( D12, [ (), (1,2)(3,4), (1,3)(4,6), (1,4)(5,6) ] ) > # although the result is mathematically a group it is returned as a > ; # proper set because the second argument is not regarded as a group [ (), (1,3)(4,6) ] gap> Intersection( Group( () ), [1,2,3] ); [ ] gap> Intersection( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] ) > ; # two or more lists or collections as arguments are legal [ ] gap> Intersection( [ [1,2,4], [2,3,4], [1,3,4] ] ) > ; # or one list of lists or collections [ 4 ] \endexample \>Union( <C1>, <C2> ... ) F \>Union( <list> ) F \>Union2( <C1>, <C2> ) O In the first form `Union' returns the union of the collections <C1>, <C2>, etc. In the second form <list> must be a list of collections and `Union' returns the union of those collections. Each argument or element of <list> respectively may also be a homogeneous list that is not a proper set, in which case `Union' silently applies `Set' (see~"Set") to it first. The result of `Union' is the set of elements that lie in any of the collections <C1>, <C2>, etc. If the result is a list then it is mutable and new, i.e., not identical to any of <C1>, <C2>, etc. Methods can be installed for the operation `Union2' that takes only two arguments. `Union' calls `Union2'. \index{union!of collections} \beginexample gap> Union( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) ); [ (), (2,3), (1,2), (1,2,3), (1,2,3,4), (1,3,2), (1,3) ] gap> Union( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] ) > ; # two or more lists or collections as arguments are legal [ 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20, 25 ] gap> Union( [ [1,2,4], [2,3,4], [1,3,4] ] ) > ; # or one list of lists or collections [ 1, 2, 3, 4 ] gap> Union( [ ] ); [ ] \endexample \>Difference( <C1>, <C2> ) O `Difference' returns the set difference of the collections <C1> and <C2>. Either argument may also be a homogeneous list that is not a proper set, in which case `Difference' silently applies `Set' (see~"Set") to it first. The result of `Difference' is the set of elements that lie in <C1> but not in <C2>. Note that <C2> need not be a subset of <C1>. The elements of <C2>, however, that are not elements of <C1> play no role for the result. If the result is a list then it is mutable and new, i.e., not identical to <C1> or <C2>. \index{set difference!of collections} \beginexample gap> Difference( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) ); [ (1,2,3,4) ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Membership Test for Collections} \indextt{\\in!operation for testing membership} \>`<obj> in <C>'{in!for collections}@{`in'!for collections} \>`\\in( <obj>, <C> )'{in!operation for}@{`in'!operation for} O returns `true' if the object <obj> lies in the collection <C>, and `false' otherwise. The infix version of the command calls the operation `\\in', for which methods can be installed. \beginexample gap> 13 in Integers; [ 1, 2 ] in Integers; true false gap> g:= Group( (1,2) );; (1,2) in g; (1,2,3) in g; true false \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Random Elements} \index{random element!of a list or collection} \>`Random( <C> )'{Random![coll]}@{`Random'!`[coll]'} O \>`Random( <list> )'{Random![coll]}@{`Random'!`[coll]'} O `Random' returns a (pseudo-)random element of the collection <C> respectively the list <list>. The distribution of elements returned by `Random' depends on the argument. For a list <list>, all elements are equally likely. The same holds usually for finite collections <C> that are not lists. For infinite collections <C> some reasonable distribution is used. See the chapters of the various collections to find out which distribution is being used. For some collections ensuring a reasonable distribution can be difficult and require substantial runtime. If speed at the cost of equal distribution is desired, the operation `PseudoRandom' should be used instead. Note that `Random' is of course *not* an attribute. \beginexample gap> Random(Rationals); 4 gap> g:= Group( (1,2,3) );; Random( g ); Random( g ); (1,3,2) () \endexample \>StateRandom( ) F \>RestoreStateRandom( <obj> ) F [This interface to the global random generator is kept for compatibility with older versions of {\GAP}. Use now `State(GlobalRandomSource)' and `Reset(GlobalRandomSource, <obj>)' instead.] For debugging purposes, it can be desirable to reset the random number generator to a state it had before. `StateRandom' returns a {\GAP} object that represents the current state of the random number generator used by `RandomList'. By calling `RestoreStateRandom' with this object as argument, the random number is reset to this same state. (The same result can be obtained by accessing the two global variables `R_N' and `R_X'.) (The format of the object used to represent the random generator seed is not guaranteed to be stable between different machines or versions of {\GAP}. \beginexample gap> seed:=StateRandom();; gap> List([1..10],i->Random(Integers)); [ -2, 1, -2, -1, 0, 1, 0, 1, -1, 0 ] gap> List([1..10],i->Random(Integers)); [ 2, 0, 4, -1, -3, 1, -4, -1, 5, -2 ] gap> RestoreStateRandom(seed); gap> List([1..10],i->Random(Integers)); [ -5, -2, 0, 1, -2, -1, -3, -2, 0, 0 ] \endexample \>PseudoRandom( <C> ) O \>PseudoRandom( <list> ) O `PseudoRandom' returns a pseudo random element of the collection <C> respectively the list <list>, which can be roughly described as follows. For a list <list>, `PseudoRandom' returns the same as `Random'. For collections <C> that are not lists, the elements returned by `PseudoRandom' are *not* necessarily equally distributed, even for finite collections <C>; the idea is that `Random' (see~"Random") returns elements according to a reasonable distribution, `PseudoRandom' returns elements that are cheap to compute but need not satisfy this strong condition, and `Representative' (see~"Representative") returns arbitrary elements, probably the same element for each call. \medskip The method used by {\GAP} to obtain random elements may depend on the type object. Many random methods in the library are eventually based on the function `RandomList'. As `RandomList' is restricted to lists of up to $2^{28}$ elements, this may create problems for very large collections. Also note that the method used by `RandomList' is intended to provide a fast algorithm rather than to produce high quality randomness for statistical purposes. If you implement your own `Random' methods we recommend that they initialize their seed to a defined value when they are loaded to permit to reproduce calculations even if they involved random elements. \>RandomList( <list> ) F \index{random seed} For a dense list <list> of up to $2^{28}$ elements, `RandomList' returns a (pseudo-)random element with equal distribution. The algorithm used is an additive number generator (Algorithm A in section~3.2.2 of \cite{TACP2} with lag 30) This random number generator is (deliberately) initialized to the same values when {\GAP} is started, so different runs of {\GAP} with the same input will always produce the same result, even if random calculations are involved. See `StateRandom' for a description on how to reset the random number generator to a previous state. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Iterators} \>Iterator( <C> ) O \>Iterator( <list> ) O Iterators provide a possibility to loop over the elements of a (countable) collection <C> or a list <list>, without repetition. For many collections <C>, an iterator of <C> need not store all elements of <C>, for example it is possible to construct an iterator of some infinite domains, such as the field of rational numbers. `Iterator' returns a mutable *iterator* <iter> for its argument. If this is a list <list> (which may contain holes), then <iter> iterates over the elements (but not the holes) of <list> in the same order (see~"IteratorList" for details). If this is a collection <C> but not a list then <iter> iterates over the elements of <C> in an unspecified order, which may change for repeated calls of `Iterator'. Because iterators returned by `Iterator' are mutable (see~"Mutability and Copyability"), each call of `Iterator' for the same argument returns a *new* iterator. Therefore `Iterator' is not an attribute (see~"Attributes"). The only operations for iterators are `IsDoneIterator', `NextIterator', and `ShallowCopy'. In particular, it is only possible to access the next element of the iterator with `NextIterator' if there is one, and this can be checked with `IsDoneIterator' (see~"NextIterator"). For an iterator <iter>, `ShallowCopy( <iter> )' is a mutable iterator <new> that iterates over the remaining elements independent of <iter>; the results of `IsDoneIterator' for <iter> and <new> are equal, and if <iter> is mutable then also the results of `NextIterator' for <iter> and <new> are equal; note that `=' is not defined for iterators, so the equality of two iterators cannot be checked with `='. When `Iterator' is called for a *mutable* collection <C> then it is not defined whether <iter> respects changes to <C> occurring after the construction of <iter>, except if the documentation explicitly promises a certain behaviour. The latter is the case if the argument is a mutable list <list> (see~"IteratorList" for subtleties in this case). It is possible to have `for'-loops run over mutable iterators instead of lists. In some situations, one can construct iterators with a special succession of elements, see~"IteratorByBasis" for the possibility to loop over the elements of a vector space w.r.t.~a given basis. For lists, `Iterator' is implemented by `IteratorList( <list> )'. For collections that are not lists, the default method is `IteratorList( Enumerator( <C> ) )'. Better methods depending on <C> should be provided if possible. For random access to the elements of a (possibly infinite) collection, *enumerators* are used. See~"Enumerators" for the facility to compute a list from <C>, which provides a (partial) mapping from <C> to the positive integers. \beginexample gap> iter:= Iterator( GF(5) ); <iterator> gap> l:= [];; gap> for i in iter do Add( l, i ); od; l; [ 0*Z(5), Z(5)^0, Z(5), Z(5)^2, Z(5)^3 ] gap> iter:= Iterator( [ 1, 2, 3, 4 ] );; l:= [];; gap> for i in iter do > new:= ShallowCopy( iter ); > for j in new do Add( l, j ); od; > od; l; [ 2, 3, 4, 3, 4, 4 ] \endexample \>IteratorSorted( <C> ) O \>IteratorSorted( <list> ) O `IteratorSorted' returns a mutable iterator. The argument must be a collection <C> or a list <list> that is not necessarily dense but whose elements lie in the same family (see~"Families"). It loops over the different elements in sorted order. For collections <C> that are not lists, the generic method is `IteratorList( EnumeratorSorted( <C> ) )'. \>IsIterator( <obj> ) C Every iterator lies in the category `IsIterator'. \>IsDoneIterator( <iter> ) O If <iter> is an iterator for the list or collection $C$ then `IsDoneIterator( <iter> )' is `true' if all elements of $C$ have been returned already by `NextIterator( <iter> )', and `false' otherwise. \>NextIterator( <iter> ) O Let <iter> be a mutable iterator for the list or collection $C$. If `IsDoneIterator( <iter> )' is `false' then `NextIterator' is applicable to <iter>, and the result is the next element of $C$, according to the succession defined by <iter>. If `IsDoneIterator( <iter> )' is `true' then it is not defined what happens if `NextIterator' is called for <iter>; that is, it may happen that an error is signalled or that something meaningless is returned, or even that {\GAP} crashes. \>IteratorList( <list> ) F `IteratorList' returns a new iterator that allows iteration over the elements of the list <list> (which may have holes) in the same order. If <list> is mutable then it is in principle possible to change <list> after the call of `IteratorList'. In this case all changes concerning positions that have not yet been reached in the iteration will also affect the iterator. For example, if <list> is enlarged then the iterator will iterate also over the new elements at the end of the changed list. *Note* that changes of <list> will also affect all shallow copies of <list>. \>TrivialIterator( <elm> ) F is a mutable iterator for the collection `[ <elm> ]' that consists of exactly one element <elm> (see~"IsTrivial"). \beginexample gap> iter:= Iterator( [ 1, 2, 3, 4 ] ); <iterator> gap> sum:= 0;; gap> while not IsDoneIterator( iter ) do > sum:= sum + NextIterator( iter ); > od; gap> IsDoneIterator( iter ); sum; true 10 gap> ir:= Iterator( Rationals );; gap> l:= [];; for i in [1..20] do Add( l, NextIterator( ir ) ); od; l; [ 0, 1, -1, 1/2, 2, -1/2, -2, 1/3, 2/3, 3/2, 3, -1/3, -2/3, -3/2, -3, 1/4, 3/4, 4/3, 4, -1/4 ] gap> for i in ir do > if DenominatorRat( i ) > 10 then break; fi; > od; gap> i; 1/11 \endexample \>IteratorByFunctions( <record> ) F `IteratorByFunctions' returns a (mutable) iterator <iter> for which `NextIterator', `IsDoneIterator', and `ShallowCopy' are computed via prescribed functions. Let <record> be a record with at least the following components. \beginitems `NextIterator' & a function taking one argument <iter>, which returns the next element of <iter> (see~"NextIterator"); for that, the components of <iter> are changed, `IsDoneIterator' & a function taking one argument <iter>, which returns `IsDoneIterator( <iter> )' (see~"IsDoneIterator"); `ShallowCopy' & a function taking one argument <iter>, which returns a record for which `IteratorByFunctions' can be called in order to create a new iterator that is independent of <iter> but behaves like <iter> w.r.t. the operations `NextIterator' and `IsDoneIterator'. \enditems Further (data) components may be contained in <record> which can be used by these function. `IteratorByFunctions' does *not* make a shallow copy of <record>, this record is changed in place (see~"prg:Creating Objects" in ``Programming in {\GAP}''). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E