[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Accessing and Modifying Sets

### Accessing and Modifying Sets

Enumerated sets can be modified by inserting or removing elements. Indexed sets allow some sequence-like operators for modification and access.

#### Accessing Sets and their Associated Structures

##### # R : SetEnum -> RngIntElt
Cardinality of the enumerated or indexed set R.
##### Type(S) : Obj -> Cat
The category of the object S. For a set this will be one of SetEnum, SetIndx, or SetForm, and for a set element it will be one of SetEnumElt, SetIndxElt, or SetFormElt. For a power set the type is PowSetEnum.
##### Parent(R) : Set -> Struct
Returns the parent structure of R, that is, the structure consisting of all (enumerated) sequences over the universe of R.
##### Universe(R) : Set -> Struct
Returns the `universe' of the (enumerated or indexed or formal) set R, that is, the common structure to which all elements of the set belong. An error is signalled when R is the null set.
##### Position(S, x) : SetIndx, Elt -> RngIntElt
Given an indexed set S, and an element x, returns the index i such that S[i]=x if such index exists, or return 0 if x is not in S. If x is not in the universe of S, an attempt will be made to coerce it; an error occurs if this fails.
##### S[i] : SetIndx, RngIntElt -> Elt
Return the i-th entry of indexed set S. If i < 1 or i > #S an error occurs. Note that indexing is not allowed on the left hand side.

### Example Set_Miscellaneous (H4E6)

We build an indexed set of sets to illustrate the use of the above functions.

```> B := {@ { i : i in [1..k] } : k in [1..5] @};
> print B;
{@
{ 1 },
{ 1, 2 },
{ 1, 2, 3 },
{ 1, 2, 3, 4 },
{ 1, 2, 3, 4, 5 },
@}
> print #B;
5
> print Universe(B);
Set of subsets of Integer Ring
> print Parent(B);
Set of indexed subsets of Set of subsets of Integer Ring
> print Category(B);
SetIndx
> print Index(B, { 2, 1 });
2
> print #B[2];
2
> print Universe(B[2]);
Integer Ring
```

#### Selecting Elements of Sets

Most finite structures in Magma, including enumerated sets, allow one to obtain a random element using Random. There is an alternative (and often preferable) option for enumerated sets in the random{ } constructor. This makes it possible to choose a random element of the set without generating the whole set first.

Likewise, rep{ } is an alternative to the general Rep function returning a representative element of a structure, having the advantage of aborting the construction of the set as soon as one element has been found.

Here, E will again be an enumerable structure, that is, a structure that allows enumeration of its elements (see the Appendix for an exhaustive list).

Note that random{ e(x) : x in E | P(x) } does not return a random element of the set of values e(x), but rather a value of e(x) for a random x in E which satisfies P (and mutatis mutandis for rep).

See the subsection on Notation in the Introduction for conventions regarding e, x, E, P.

##### Random(R) : SetEnum -> Elt
A random element chosen from the enumerated or indexed set R. Every element has an equal probability of being chosen. Successive invocations of the function will result in independently chosen elements being returned as the value of the function. If R is empty an error occurs.
##### random{ e(x) : x in E | P(x) }
Given an enumerated structure E and a Boolean expression P, return the value of the expression e(y) for a randomly chosen element y of E for which P(y) is true.

P may be omitted if it is always true.

##### random{ e(x_1, ..., x_k) : x_1 in E_1, ..., x_k in E_k | P(x_1, ..., x_k) }
Given enumerated structures E_1, ..., E_k, and a Boolean expression P(x_1, ..., x_k), return the value of the expression e(y_1, ..., y_k) for a randomly chosen element < y_1, ..., y_k > of E_1 x ... x E_k, for which P(y_1, ..., y_k) is true.

P may be omitted if it is always true.

If successive structures E_i and E_(i + 1) are identical, then the abbreviation x_i, x_(i + 1) in E_i may be used.

### Example Set_Random (H4E7)

Here are two ways to find a `random' primitive element for a finite field.

```> p := 10007;
> F := FiniteField(p);
> proots := { z : z in F | IsPrimitive(z) };
> print #proots;
5002
> print Random(proots);
5279
```
This way, a set of 5002 elements is built (and primitivity is checked for all elements of F), and a random choice is made. Alternatively, we use random.

```> print random{ x : x in F | IsPrimitive(x) };
4263
```
In this case random elements in F are chosen until one is found that is primitive. Since almost half of F's elements are primitive, only very few primitivity tests will be done before success occurs.
##### Rep(R) : SetEnum -> Elt
An arbitrary element chosen from the enumerated or indexed set R.
##### ExtractRep(~R, ~r) : SetEnum, Elt ->
Assigns an arbitrary element chosen from the enumerated set R to r, and removes it from R. Thus the set R is modified, as well as the element r. An error occurs if R is empty.
##### rep{ e(x) : x in E | P(x) }
Given an enumerated structure E and a Boolean expression P, return the value of the expression e(y) for the first element y of E for which P(y) is true. If P(x) is false for every element of E, an error will occur.
##### rep{ e(x_1, ..., x_k) : x_1 in E_1, ..., x_k in E_k | P(x_1, ..., x_k) }
Given enumerated structures E_1, ..., E_k, and a Boolean expression P(x_1, ..., x_k), return the value of the expression e(y_1, ..., y_k) for the first element < y_1, ..., y_k > of E_1 x ... x E_k, for which P(y_1, ..., y_k) is true. An error occurs if no element of E_1 x ... x E_k satisfies P.

P may be omitted if it is always true.

If successive structures E_i and E_(i + 1) are identical, then the abbreviation x_i, x_(i + 1) in E_i may be used.

### Example Set_ExtractRep (H4E8)

As an illustration of the use of ExtractRep, we modify an earlier example, and find cubes satisfying x^3 + y^3=z^3 - 1 (with x, y, z <= 1000).

```> cubes := { Integers() | x^3 : x in [1..1000] };
> cc := cubes;
> min := { };
> while not IsEmpty(cc) do
>    ExtractRep(~cc, ~a);
>    for b in cc do
>       if a+b+1 in cubes then
>          min join:= { <a, b> };
>       end if;
>    end for;
> end while;
> print { < Iroot(x[1], 3), Iroot(x[2], 3) > : x in min };
{ <138, 135>, <823, 566>, <426, 372>, <242, 720>,
<138, 71>, <426, 486>, <6, 8> }
```
Note that instead of taking cubes over again, we only have to take cube roots in the last line (on the small resulting set) once.
##### Min(S) : SetEnum -> Elt
Given a non-empty, enumerated or indexed set S, such that lt and eq are defined on the universe of S, this function returns the minimum of the elements of S. If S is an indexed set, the position of the minimum is also returned.
##### Max(S) : SetEnum -> Elt
Given a non-empty, enumerated or indexed set S, such that lt and eq are defined on the universe of S, this function returns the maximum of the elements of S. If S is an indexed set, the position of the maximum is also returned.
##### Hash(x) : Elt -> RngIntElt
Given a Magma object x which can be placed in a set, return the hash value of x used by the set machinery. This is a fixed but arbitrary non-negative integer (whose maximum value is the maximum value of a C unsigned long on the particular machine). The crucial property is that if x and y are objects and x equals y then the hash values of x and y are equal (even if x and y have different internal structures). Thus one could implement sets manually if desired by the use of this function.

#### Modifying Sets

##### Include(S, x) : SetEnum, Elt -> SetEnum
Create the enumerated or indexed set obtained by putting the element x in (S is unchanged if x is already in S). If S is an indexed set, the element will be appended at the end. If x is not in the universe of S, an attempt will be made to coerce it; an error occurs if this fails.

There are two versions of this: a procedure, where S is replaced by the new set, and a function, which returns the new set. The procedural version takes a reference ~S to S as an argument.

Note that the procedural version is much more efficient since the set S will not be copied.

##### Exclude(S, x) : SetEnum, Elt -> SetEnum
Create an enumerated set by removing the element x from S; nothing happens if x is not in S. If x is not in the universe of S, an attempt will be made to coerce it; an error occurs if this fails.

There are two versions of this: a procedure, where S is replaced by the new set, and a function, which returns the new set. The procedural version takes a reference ~S to S as an argument.

Note that the procedural version is much more efficient since the set S will not be copied.

##### ChangeUniverse(S, V) : SetEnum, Str -> SetEnum
Given an enumerated or indexed set S with universe U and a structure V which contains U, construct a new enumerated or indexed set which consists of the elements of S coerced into V.

There are two versions of this: a procedure, where S is replaced by the new set, and a function, which returns the new set. The procedural version takes a reference ~S to S as an argument.

Note that the procedural version is much more efficient since the set S will not be copied.

### Example Set_Include (H4E9)

This example uses Include and Exclude to find a set (if it exists) of cubes of integers such that the elements of a given set R can be expressed as the sum of two of those.

```> R := { 218, 271, 511 };
> x := 0;
> cubes := { 0 };
> while not IsEmpty(R) do
>    x +:= 1;
>    c := x^3;
>    Include(~cubes, c);
>    Include(~cubes, -c);
>    for z in cubes do
>        Exclude(~R, z+c);
>        Exclude(~R, z-c);
>    end for;
> end while;
```
We did not record how the elements of R were obtained as sums of a pair of cubes. For that, the following suffices.

```> R := { 218, 271, 511 }; // it has been emptied !
> print { { x, y } : x, y in cubes | x+y in R };
{
{ -729, 1000 },
{ -125, 343 },
{ -1, 512 },
}
```

##### SetToIndexedSet(E) : SetEnum -> SetIndx
Given an enumerated set E, this function returns an indexed set with the same elements (and universe) as E.
##### Isetset(S) : SetIndx -> SetEnum
Given an indexed set S, this function returns an enumerated set with the same elements (and universe) as E.
##### Isetseq(S) : SetIndx -> SeqEnum
Given an indexed set S, this function returns a sequence with the same elements (and universe) as E.
[Next] [Prev] [Right] [Left] [Up] [Index] [Root]