|
Enumerated sets can be modified by inserting or removing
elements. Indexed sets allow some sequence-like operators
for modification and access.
# 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.
Type(S) : Any -> Cat
The category of the object S. For a set this will be one of
SetEnum, SetIndx, SetMulti, or SetFormal.
For a power set the type is one of PowSetEnum, PowSetIndx,
PowSetMulti.
Returns the parent structure of R, that is, the structure
consisting of all (enumerated) sequences over the universe of R.
Returns the `universe' of the (enumerated or indexed or multi- 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.
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.
The indexed set {S[i1], ..., S[ir]} 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.
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] @};
> 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
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) for
conventions regarding e, x, E, P.
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.
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.
Given enumerated structures E1, ..., Ek, and a Boolean expression
P(x1, ..., xk), return the value of the expression
e(y1, ..., yk) for a randomly chosen element
< y1, ..., yk > of
E1 x ... x Ek, for which P(y1, ..., yk)
is true.
The expression P may be omitted if it is always true.
If successive structures Ei and Ei + 1 are identical, then
the abbreviation xi, xi + 1 in Ei may be used.
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) };
> #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.
> 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) : SetIndx -> Elt
Representative(R) : SetEnum -> Elt
Rep(R) : SetEnum -> Elt
An arbitrary element chosen from the enumerated, indexed, or multi- set R.
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.
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.
Given enumerated structures E1, ..., Ek, and a Boolean expression
P(x1, ..., xk), return the value of the expression
e(y1, ..., yk) for the first element
< y1, ..., yk > of
E1 x ... x Ek, for which P(y1, ..., yk)
is true.
An error occurs if no element of E1 x ... x Ek satisfies
P.
The expression P may be omitted if it is always true.
If successive structures Ei and Ei + 1 are identical, then
the abbreviation xi, xi + 1 in Ei may be used.
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;
> { < 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) : 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.
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.
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.
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
~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
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
~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
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
~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) : 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.
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 !
> { { x, y } : x, y in cubes | x+y in R };
{
{ -729, 1000 },
{ -125, 343 },
{ -1, 512 },
}
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.
Given a multiset S, this function returns an enumerated set
with the same elements (and universe) as S.
Given an enumerated set E, this function returns a multiset
with the same elements (and universe) as E.
Given an enumerated sequence E, this function returns a multiset
with the same elements (and universe) as E.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|