# 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: SetIndx -> RngIntElt` ### `# R: SetEnum -> RngIntElt` ### `# R: SetMulti -> RngIntElt` Cardinality of the enumerated, indexed, or multi- set $R$. Note that for a multiset, repetitions are significant, so the result may be greater than the underlying set. ### `Category(S): Any -> Cat` ### `Type(S): Any -> Cat` The category of the object $S$. For a set this will be one of `SetEnum`, `SetIndx`, or `SetMulti`. For a power set the type is one of `PowSetEnum`, `PowSetIndx`, `PowSetMulti`. ### `Parent(R): Set -> Str` Returns the parent structure of $R$, that is, the structure consisting of all (enumerated) subsets of the universe of $R$. ### `Universe(R): Set -> Str` Returns the ‘universe’ of the (enumerated or indexed or multi-) 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. ### `Index(S, x): SetIndx, Elt -> RngIntElt` ### `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. ### `S[I]: SetIndx, [RngIntElt] -> SetIndx` The indexed set $\{S[i_1], \ldots, S[i_r]\}$ consisting of terms selected from the indexed set $S$, according to the terms of the integer sequence $I$. If any term of $I$ lies outside the range 1 to $\#S$, then an error results. If $I$ is the empty sequence, then the empty set with universe the same as that of $S$ is returned. ### `Example: Miscellaneous (ex-3d41ac)` We build an indexed set of sets to illustrate the use of the above functions. ```magma > B := { @ { i : i in [1..k] } : k in [1..5] @}; > B; { @ { 1 }, { 1, 2 }, { 1, 2, 3 }, { 1, 2, 3, 4 }, { 1, 2, 3, 4, 5 }, @} > #B; 5 > Universe(B); Set of subsets of Integer Ring > Parent(B); Set of indexed subsets of Set of subsets of Integer Ring > Category(B); SetIndx > Index(B, { 2, 1}); 2 > #B[2]; 2 > 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 (Chapter [Introduction to Aggregates](../IntroductionToAggregates/index-introduction-to-aggregates.md#chapaggr)) for conventions regarding $e, x, E, P$. ### `Random(R): SetIndx -> Elt` ### `Random(R): SetEnum -> Elt` A random element chosen from the enumerated, indexed or multi- set $R$. Every element has an equal probability of being chosen for enumerated or indexed sets, and a weighted probability in proportion to its multiplicity for multisets. 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. The expression $P$ may be omitted if it is always true. ### `random{ e(x₁, ..., xₖ) : x₁ in E₁, ..., xₖ in Eₖ | P(x₁, ..., xₖ) }` Given enumerated structures $E_1, \ldots, E_k$, and a Boolean expression $P(x_1$, $\ldots$, $x_k)$, return the value of the expression $e(y_1, \cdots, y_k)$ for a randomly chosen element $< y_1, \ldots, y_k >$ of $E_1 \times \cdots \times E_k$, for which $P(y_1, \ldots, y_k)$ is true. The expression $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: Random (ex-1b553f)` Here are two ways to find a ‘random’ primitive element for a finite field. ```magma > p := 10007; > F := FiniteField(p); > proots := { z : z in F | IsPrimitive(z) }; > #proots; 5002 > 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`. ```magma > 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. ### `Representative(R): SetIndx -> Elt` ### `Rep(R): SetIndx -> Elt` ### `Representative(R): SetEnum -> Elt` ### `Rep(R): SetEnum -> Elt` An arbitrary element chosen from the enumerated, indexed, or multi- 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₁, ..., xₖ) : x₁ in E₁, ..., xₖ in Eₖ | P(x₁, ..., xₖ) }` Given enumerated structures $E_1, \ldots, E_k$, and a Boolean expression $P(x_1$, $\ldots$, $x_k)$, return the value of the expression $e(y_1, \cdots, y_k)$ for the first element $< y_1, \ldots, y_k >$ of $E_1 \times \cdots \times E_k$, for which $P(y_1, \ldots, y_k)$ is true. An error occurs if no element of $E_1 \times \cdots \times E_k$ satisfies $P$. The expression $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: Extract Rep (ex-e07b22)` 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 \leq 1000$). ```magma > 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:= { }; > end if; > end for; > end while; > { < 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. ### `Minimum(S): SetIndx -> Elt, RngIntElt` ### `Min(S): SetIndx -> Elt, RngIntElt` ### `Minimum(S): SetEnum -> Elt` ### `Min(S): SetEnum -> Elt` ### `Minimum(S): SetMulti -> Elt` ### `Min(S): SetMulti -> Elt` Given a non-empty enumerated, indexed, or multi- 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. ### `Maximum(S): SetIndx -> Elt, RngIntElt` ### `Max(S): SetIndx -> Elt, RngIntElt` ### `Maximum(S): SetEnum -> Elt` ### `Max(S): SetEnum -> Elt` ### `Maximum(S): SetMulti -> Elt` ### `Max(S): SetMulti -> Elt` Given a non-empty enumerated, indexed, or multi- 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` ### `Include(S, x): SetEnum, Elt -> SetEnum` ### `Include(~S, x): SetIndx, Elt` ### `Include(S, x): SetIndx, Elt -> SetIndx` ### `Include(~S, x): SetMulti, Elt` ### `Include(S, x): SetMulti, Elt -> SetMulti` Create the enumerated, indexed, or multi- set obtained by putting the element $x$ in $S$ ($S$ is unchanged if $S$ is not a multiset and $x$ is already in $S$). If $S$ is an indexed set, the element will be appended at the end. If $S$ is a multiset, the multiplicity of $x$ will be increased accordingly. 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 $\sim 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` ### `Exclude(S, x): SetEnum, Elt -> SetEnum` ### `Exclude(~S, x): SetMulti, Elt` ### `Exclude(S, x): SetMulti, Elt -> SetMulti` Create a new set by removing the element $x$ from $S$. If $S$ is an enumerated set, nothing happens if $x$ is not in $S$. If $S$ is a multiset, the multiplicity of $x$ will be decreased accordingly. 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 $\sim 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` ### `ChangeUniverse(S, V): SetEnum, Str -> SetEnum` ### `ChangeUniverse(~S, V): SetIndx, Str` ### `ChangeUniverse(S, V): SetIndx, Str -> SetIndx` ### `ChangeUniverse(~S, V): SetMulti, Str` ### `ChangeUniverse(S, V): SetMulti, Str -> SetMulti` Given an enumerated, indexed, or multi- set $S$ with universe $U$ and a structure $V$ which contains $U$, construct a new set of the same type 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 $\sim S$ to $S$ as an argument. Note that the procedural version is much more efficient since the set $S$ will not be copied. ### `CanChangeUniverse(S, V): SetEnum, Str -> Bool, SeqEnum` ### `CanChangeUniverse(S, V): SetIndx, Str -> Bool, SeqEnum` ### `CanChangeUniverse(S, V): SetMulti, Str -> Bool, SeqEnum` Given an enumerated, indexed, or multi- set $S$ with universe $U$ and a structure $V$ which contains $U$, attempt to construct a new set $T$ of the same type which consists of the elements of $S$ coerced into $V$; if successful, return `true` and $T$, otherwise return `false`. ### `Example: Include (ex-708b1a)` 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. ```magma > 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. ```magma > R := { 218, 271, 511 }; // it has been emptied ! > { { 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$. ### `IndexedSetToSet(S): SetIndx -> SetEnum` ### `Isetset(S): SetIndx -> SetEnum` Given an indexed set $S$, this function returns an enumerated set with the same elements (and universe) as $S$. ### `IndexedSetToSequence(S): SetIndx -> SeqEnum` ### `Isetseq(S): SetIndx -> SeqEnum` Given an indexed set $S$, this function returns a sequence with the same elements (and universe) as $S$. ### `MultisetToSet(S): SetMulti -> SetEnum` Given a multiset $S$, this function returns an enumerated set with the same elements (and universe) as $S$. ### `SetToMultiset(E): SetEnum -> SetMulti` Given an enumerated set $E$, this function returns a multiset with the same elements (and universe) as $E$. ### `SequenceToMultiset(Q): SeqEnum -> SetMulti` Given an enumerated sequence $E$, this function returns a multiset with the same elements (and universe) as $E$.