Searching objects in a list works much quicker if the list is known to be
sorted.
Currently GAP exploits the sortedness of a list automatically only if
the list is strictly sorted, which is indicated by the property
IsSSortedList, see IsSSortedList.
Remember that a list of mutable objects cannot store that it is strictly
sorted but has to test it anew whenever it is asked whether it is sorted,
see the remark in Properties and Attributes for Lists.
Therefore GAP cannot take advantage of the sortedness of a list if this
list has mutable entries.
Moreover, if a sorted list list with mutable elements is used as an argument
of a function that expects this argument to be sorted,
for example UniteSet or RemoveSet (see UniteSet, RemoveSet),
then it is checked whether list is in fact sorted;
this check can have the effect actually to slow down the computations,
compared to computations with sorted lists of immutable elements
or computations that do not involve functions that do automatically check
sortedness.
Strictly sorted lists are used to represent sets in GAP. More precisely, a strictly sorted list is called a proper set in the following, in order to avoid confusion with domains (see Domains) which also represent sets.
In short proper sets are represented by sorted lists without holes and duplicates in GAP. 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 without holes that may have duplicates.
This section lists only those functions that are defined exclusively for
proper sets.
Set theoretic functions for general collections, such as Intersection
and Union, are described in Chapter Collections.
In particular, for the construction of proper sets, see SSortedList
and AsSSortedList.
For finding positions in sorted lists, see PositionSorted.
in list
The element test for strictly sorted lists uses binary search.
The following functions, if not explicitly stated differently,
take two arguments, set and obj, where set must be a proper set,
otherwise an error is signalled;
If the second argument obj is a list that is not a proper set then
Set (see Set) is silently applied to it first (see Set).
IsEqualSet( list1, list2 ) O
tests whether list1 and list2 are equal when viewed as sets, that
is if every element of list1 is an element of list2 and vice versa.
Either argument of IsEqualSet may also be a list that is not a proper
set, in which case Set (see Set) is applied to it first.
If both lists are proper sets then they are of course equal if and only
if they are also equal as lists.
Thus IsEqualSet( list1, list2 ) is equivalent to
Set( list1 ) = Set( list2 ) (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
IsSubsetSet( list1, list2 ) O
tests whether every element of list2 is contained in list1.
Either argument of IsSubsetSet may also be a list that is not a proper
set, in which case Set (see Set) is applied to it first.
AddSet( set, obj ) O
adds the element obj to the proper set set. If obj is already contained in set then set is not changed. Otherwise obj is inserted at the correct position such that set is again a proper set afterwards.
Note that obj must be in the same family as each element of set.
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( set, obj ) O
removes the element obj from the proper set set. If obj is not contained in set then set is not changed. If obj is an element of set 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 ); s; [ 2, 3, 4, 5, 7 ] gap> RemoveSet( s, 10 ); s; [ 2, 3, 4, 5, 7 ]
UniteSet( set, list ) O
unites the proper set set with list. This is equivalent to adding all elements of list to set (see AddSet).
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 ]
IntersectSet( set, list ) O
intersects the proper set set with list. This is equivalent to removing from set all elements of set that are not contained in list.
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 ]
SubtractSet( set, list ) O
subtracts list from the proper set set. This is equivalent to removing from set all elements of list.
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 ]
There are nondestructive counterparts of the functions UniteSet,
IntersectSet, and SubtractSet available for proper sets.
These are UnionSet, IntersectionSet, and Difference.
The former two are methods for the more general operations Union
and Intersection (see Union, Intersection),
the latter is itself an operation (see Difference).
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 the first argument set.
If set is not a proper set it is not specified to which of a number
of equal elements in set the element in the result is identical
(see Identical Lists).
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual