%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A set.tex GAP documentation Martin Schoenert %% %A @(#)$Id: set.tex,v 3.7 1994/05/30 14:52:41 vfelsch Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes those functions that mainly deal with proper sets. %% %H $Log: set.tex,v $ %H Revision 3.7 1994/05/30 14:52:41 vfelsch %H index entries rearranged %H %H Revision 3.6 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.5 1993/02/04 16:03:43 felsch %H examples fixed %H %H Revision 3.4 1992/04/02 21:06:23 martin %H changed *domain functions* to *set theoretic functions* %H %H Revision 3.3 1991/12/27 16:07:04 martin %H revised everything for GAP 3.1 manual %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:33:34 martin %H Initial revision under RCS %H %% \Chapter{Sets}% \index{multisets} A very important mathematical concept, maybe the most important of all, are sets. Mathematically a *set* is an abstract object such that each object is either an element of the set or it is not. So a set is a collection like a list, and in fact {\GAP} uses lists to represent sets. Note that this of course implies that {\GAP} only deals with finite sets. Unlike a list a set must not contain an element several times. It simply makes no sense to say that an object is twice an element of a set, because an object is either an element of a set, or it is not. Therefore the list that is used to represent a set has no duplicates, that is, no two elements of such a list are equal. Also unlike a list a set does not impose any ordering on the elements. Again it simply makes no sense to say that an object is the first or second etc. element of a set, because, again, an object is either an element of a set, or it is not. Since ordering is not defined for a set we can put the elements in any order into the list used to represent the set. We put the elements sorted into the list, because this ordering is very practical. For example if we convert a list into a set we have to remove duplicates, which is very easy to do after we have sorted the list, since then equal elements will be next to each other. In short sets are represented by sorted lists without holes and duplicates in {\GAP}. Such a list is in this document called a proper set. Note that we guarantee this representation, so you may make use of the fact that a set is represented by a sorted list in your functions. In some contexts (for example see "Combinatorics"), we also want to talk about multisets. A *multiset* is like a set, except that an element may appear several times in a multiset. Such multisets are represented by sorted lists with holes that may have duplicates. The first section in this chapter describes the functions to test if an object is a set and to convert objects to sets (see "IsSet" and "Set"). The next section describes the function that tests if two sets are equal (see "IsEqualSet"). The next sections describe the destructive functions that compute the standard set operations for sets (see "AddSet", "RemoveSet", "UniteSet", "IntersectSet", and "SubtractSet"). The last section tells you more about sets and their internal representation (see "More about Sets"). All set theoretic functions, especially 'Intersection' and 'Union', also accept sets as arguments. Thus all functions described in chapter "Domains" are applicable to sets (see "Set Functions for Sets"). Since sets are just a special case of lists, all the operations and functions for lists, especially the membership test (see "In"), can be used for sets just as well (see "Lists"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsSet}% \index{test!for a set} 'IsSet( )' 'IsSet' returns 'true' if the object is a set and 'false' otherwise. An object is a set if it is a sorted lists without holes or duplicates. Will cause an error if evaluation of is an unbound variable. | gap> IsSet( [] ); true gap> IsSet( [ 2, 3, 5, 7, 11 ] ); true gap> IsSet( [, 2, 3,, 5,, 7,,,, 11 ] ); false # this list contains holes gap> IsSet( [ 11, 7, 5, 3, 2 ] ); false # this list is not sorted gap> IsSet( [ 2, 2, 3, 5, 5, 7, 11, 11 ] ); false # this list contains duplicates gap> IsSet( 235711 ); false # this argument is not even a list | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Set}% \index{convert!to a set} 'Set( )' 'Set' returns a new proper set, which is represented as a sorted list without holes or duplicates, containing the elements of the list . 'Set' returns a new list even if the list is already a proper set, in this case it is equivalent to 'ShallowCopy' (see "ShallowCopy"). Thus the result is a new list that is not identical to any other list. The elements of the result are however identical to elements of . If contains equal elements, it is not specified to which of those the element of the result is identical (see "Identical Lists"). | gap> Set( [3,2,11,7,2,,5] ); [ 2, 3, 5, 7, 11 ] gap> Set( [] ); [ ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsEqualSet}% \index{test!for set equality} 'IsEqualSet( , )' 'IsEqualSet' returns 'true' if the two lists and are equal *when viewed as sets*, and 'false' otherwise. and are equal if every element of is also an element of and if every element of is also an element of . If both lists are proper sets then they are of course equal if and only if they are also equal as lists. Thus 'IsEqualSet( , )' is equivalent to 'Set( ) = Set( )' (see "Set"), but the former is more efficient. | gap> IsEqualSet( [2,3,5,7,11], [11,7,5,3,2] ); true gap> IsEqualSet( [2,3,5,7,11], [2,3,5,7,11,13] ); false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AddSet}% \index{add!an element to a set} 'AddSet( , )' 'AddSet' adds , which may be an elment of an arbitrary type, to the set , which must be a proper set, otherwise an error will be signalled. If is already an element of the set , the set is not changed. Otherwise is inserted at the correct position such that is again a set afterwards. | gap> s := [2,3,7,11];; gap> AddSet( s, 5 ); s; [ 2, 3, 5, 7, 11 ] gap> AddSet( s, 13 ); s; [ 2, 3, 5, 7, 11, 13 ] gap> AddSet( s, 3 ); s; [ 2, 3, 5, 7, 11, 13 ] | 'RemoveSet' (see "RemoveSet") is the counterpart of 'AddSet'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RemoveSet}% \index{remove!an element from a set} 'RemoveSet( , )' 'RemoveSet' removes the element , which may be an object of arbitrary type, from the set , which must be a set, otherwise an error will be signalled. If is not an element of nothing happens. If is an element it is removed and all the following elements in the list are moved one position forward. | gap> s := [ 2, 3, 4, 5, 6, 7 ];; gap> RemoveSet( s, 6 ); gap> s; [ 2, 3, 4, 5, 7 ] gap> RemoveSet( s, 10 ); gap> s; [ 2, 3, 4, 5, 7 ] | 'AddSet' (see "AddSet") is the counterpart of 'RemoveSet'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{UniteSet}% \index{union!of sets} 'UniteSet( , )' 'UniteSet' unites the set with the set . This is equivalent to adding all the elements in to (see "AddSet"). must be a proper set, otherwise an error is signalled. may also be list that is not a proper set, in which case 'UniteSet' silently applies 'Set' to it first (see "Set"). 'UniteSet' returns nothing, it is only called to change . | gap> set := [ 2, 3, 5, 7, 11 ];; gap> UniteSet( set, [ 4, 8, 9 ] ); set; [ 2, 3, 4, 5, 7, 8, 9, 11 ] gap> UniteSet( set, [ 16, 9, 25, 13, 16 ] ); set; [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 25 ] | The function 'UnionSet' (see "Set Functions for Sets") is the nondestructive counterpart to the destructive procedure 'UniteSet'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IntersectSet}% \index{intersection!of sets} 'IntersectSet( , )' 'IntersectSet' intersects the set with the set . This is equivalent to removing all the elements that are not in from (see "RemoveSet"). must be a set, otherwise an error is signalled. may be a list that is not a proper set, in which case 'IntersectSet' silently applies 'Set' to it first (see "Set"). 'IntersectSet' returns nothing, it is only called to change . | gap> set := [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16 ];; gap> IntersectSet( set, [ 3, 5, 7, 9, 11, 13, 15, 17 ] ); set; [ 3, 5, 7, 9, 11, 13 ] gap> IntersectSet( set, [ 9, 4, 6, 8 ] ); set; [ 9 ] | The function 'IntersectionSet' (see "Set Functions for Sets") is the nondestructive counterpart to the destructive procedure 'IntersectSet'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SubtractSet}% \index{subtract!a set from another} 'SubtractSet( , )' 'SubtractSet' subtracts the set from the set . This is equivalent to removing all the elements in from (see "RemoveSet"). must be a proper set, otherwise an error is signalled. may be a list that is not a proper set, in which case 'SubtractSet' applies 'Set' to it first (see "Set"). 'SubtractSet' returns nothing, it is only called to change . | gap> set := [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ];; gap> SubtractSet( set, [ 6, 10 ] ); set; [ 2, 3, 4, 5, 7, 8, 9, 11 ] gap> SubtractSet( set, [ 9, 4, 6, 8 ] ); set; [ 2, 3, 5, 7, 11 ] | The function 'Difference' (see "Difference") is the nondestructive counterpart to destructive the procedure 'SubtractSet'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Set Functions for Sets}% \index{test!for subsets} As was already mentioned in the introduction to this chapter all domain functions also accept sets as arguments. Thus all functions described in the chapter "Domains" are applicable to sets. This section describes those functions where it might be helpful to know the implementation of those functions for sets. 'IsSubset( , )'% \index{IsSubset!for sets} This is implemented by 'IsSubsetSet', which you can call directly to save a little bit of time. Either argument to 'IsSubsetSet' may also be a list that is not a proper set, in which case 'IsSubset' silently applies 'Set' (see "Set") to it first. 'Union( , )'% \index{union!of sets} This is implemented by 'UnionSet', which you can call directly to save a little bit of time. Note that 'UnionSet' only accepts two sets, unlike 'Union', which accepts several sets or a list of sets. The result of 'UnionSet' is a new set, represented as a sorted list without holes or duplicates. Each argument to 'UnionSet' may also be a list that is not a proper set, in which case 'UnionSet' silently applies 'Set' (see "Set") to this argument. 'UnionSet' is implemented in terms of its destructive counterpart 'UniteSet' (see "UniteSet"). 'Intersection( , )'% \index{intersection!of sets} This is implemented by 'IntersectionSet', which you can call directly to save a little bit of time. Note that 'IntersectionSet' only accepts two sets, unlike 'Intersection', which accepts several sets or a list of sets. The result of 'IntersectionSet' is a new set, represented as a sorted list without holes or duplicates. Each argument to 'IntersectionSet' may also be a list that is not a proper set, in which case 'IntersectionSet' silently applies 'Set' (see "Set") to this argument. 'IntersectionSet' is implemented in terms of its destructive counterpart 'IntersectSet' (see "IntersectSet"). The result of 'IntersectionSet' and 'UnionSet' is always a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of . If is not a proper list it is not specified to which of a number of equal elements in the element in the result is identical (see "Identical Lists"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{More about Sets} In the previous section we defined a proper set as a sorted list without holes or duplicates. This representation is not only nice to use, it is also a good internal representation supporting efficient algorithms. For example the 'in' operator can use binary instead of a linear search since a set is sorted. For another example 'Union' only has to merge the sets. However, all those set functions also allow lists that are not proper sets, silently making a copy of it and converting this copy to a set. Suppose all the functions would have to test their arguments every time, comparing each element with its successor, to see if they are proper sets. This would chew up most of the performance advantage again. For example suppose 'in' would have to run over the whole list, to see if it is a proper set, so it could use the binary search. That would be ridiculous. To avoid this a list that is a proper set may, but need not, have an internal flag set that tells those functions that this list is indeed a proper set. Those functions do not have to check this argument then, and can use the more efficient algorithms. This section tells you when a proper set obtains this flag, so you can write your functions in such a way that you make best use of the algorithms. The results of 'Set', 'Difference', 'Intersection' and 'Union' are known to be sets by construction, and thus have the flag set upon creation. If an argument to 'IsSet', 'IsEqualSet', 'IsSubset', 'Set', 'Difference', 'Intersection' or 'Union' is a proper set, that does not yet have the flag set, those functions will notice that and set the flag for this set. Note that 'in' will use linear search if the right operand does not have the flag set, will therefore not detect if it is a proper set and will, unlike the functions above, never set the flag. If you change a proper set, that does have this flag set, by assignment, 'Add' or 'Append' the set will generally lose it flag, even if the change is such that the resulting list is still a proper set. However if the set has more than 100 elements and the value assigned or added is not a list and not a record and the resulting list is still a proper set than it will keep the flag. Note that changing a list that is not a proper set will never set the flag, even if the resulting list is a proper set. Such a set will obtain the flag only if it is passed to a set function. Suppose you have built a proper set in such a way that it does not have the flag set, and that you now want to perform lots of membership tests. Then you should call 'IsSet' with that set as an argument. If it is indeed a proper set 'IsSet' will set the flag, and the subsequent 'in' operations will use the more efficient binary search. You can think of the call to 'IsSet' as a hint to {\GAP} that this list is a proper set. There is no way you can set the flag for an ordinary list without going through the checking in 'IsSet'. The internal functions depend so much on the fact that a list with this flag set is indeed sorted and without holes and duplicates that the risk would be too high to allow setting the flag without such a check. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%