This section lists functions for obtaining information about existing sequences, for modifying sequences and for creating sequences from others. Most of these operators only apply to enumerated sequences.
Returns the length of the enumerated sequence S, which is the index of the last term of S whose value is defined. The length of the empty sequence is zero.
Returns the parent structure for a sequence S, that is, the structure consisting of all (enumerated) sequences over the universe of S.
Returns the `universe' of the sequence S, that is, the common structure to which all elements of the sequence belong. This universe may itself be a set or sequence. An error is signalled when S is the null sequence.
The i-th term si of the sequence S. If i ≤0, or i > #S + 1, or S[i] is not defined, then an error results. Here i is allowed to be a multi-index (see Introduction for the interpretation). This can be used as the left hand side of an assignment: S[i] := x redefines the i-th term of the sequence S to be x. If i ≤0, then an error results. If i > n, then the sequence [s1, ..., sn, sn + 1, ..., si - 1, x] replaces S, where sn + 1, ..., si - 1 are all undefined. Here i is allowed to be a multi-index.An error occurs if x cannot be coerced into the universe of S.
Here, S denotes an enumerated sequence [s1, ..., sn]. Further, i and j are integers or multi-indices (see Introduction).
The sequence [si1, ..., sir] consisting of terms selected from the sequence 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.The effect of T := S[I] differs from that of T := [ S[i] : i in I ]: if in the first case an undefined entry occurs for i∈I between 1 and #S it will be copied over; in the second such undefined entries will lead to an error.
Given a non-empty, complete enumerated sequence S such that lt and eq are defined on the universe of S, this function returns two values: a minimal element s in S, as well as the first position i such that s=S[i].
Given a non-empty, complete enumerated sequence S such that gt and eq are defined on the universe of S, this function returns two values: a maximal element s in S, as well as the first position i such that s=S[i].
Returns either the position of the first occurrence of x in the sequence S, or zero if S does not contain x. The second variants of each function starts the search at position f. This can save time in second (and subsequent) searches for the same entry further on. If no occurrence of x in S from position f onwards is found, then zero is returned.
An (arbitrary) element chosen from the enumerated sequence R
A random element chosen from the enumerated sequence 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.
Given an enumerated sequence R of length r this function returns the r entries of the sequence (in order).
The enumerated sequence R itself. This function is just included for completeness.
The operations given here are available as both procedures and functions. In the procedure version, the given sequence is destructively modified `in place'. This is very efficient, since it is not necessary to make a copy of the sequence. In the function version, the given sequence is not changed, but a modified version of it is returned. This is more suitable if the old sequence is still required. Some of the functions also return useful but non-obvious values.
Here, S denotes an enumerated sequence, and x an element of some structure V. The modifications involving S and x will only be successful if x can be coerced into the universe of S; an error occurs if this fails. (See the Introduction to this Part).
Create an enumerated sequence by adding the object x to the end of S, i.e., the enumerated sequence [s1, ... sn, x].There are two versions of this: a procedure, where S is replaced by the appended sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Create an enumerated sequence obtained by removing the first occurrence of the object x from S, i.e., the sequence [s1, ... si - 1, si + 1, ..., sn], where si is the first term of S that is equal to x. If x is not in S then this is just S.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Create a sequence by adding the object x to the end of S, provided that no term of S is equal to x. Thus, if x does not occur in S, the enumerated sequence [s1, ..., sn, x] is created.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Create the sequence formed by inserting the object x at position i in S and moving the terms S[i], ..., S[n] down one place, i.e., the enumerated sequence [s1, ... si - 1, x, si, ..., sn]. Note that i may be bigger than the length n of S, in which case the new length of S will be i, and the entries S[n + 1], ..., S[i - 1] will be undefined.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Create the sequence [s1, ..., sk - 1, t1, ..., tl, sm + 1, ..., sn]. If k ≤0 or k > m + 1, then an error results. If k = m + 1 then the terms of T will be inserted into S immediately before the term sk. If k > n, then the sequence [s1, ..., sn, sn + 1, ..., sk - 1, t1, ..., tl] is created, where sn + 1, ..., sk - 1 are all undefined. In the case where T is the empty sequence, terms sk, ..., sm are deleted from S.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Create the enumerated sequence formed by removing the last term of the sequence S, i.e., the sequence [s1, ..., sn - 1]. An error occurs if S is empty.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Create the enumerated sequence formed by removing the i-th term from S, i.e., the sequence [s1, ... si - 1, si + 1, ..., sn]. An error occurs if i<1 or i>n.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Create the enumerated sequence formed by reversing the order of the terms in the complete enumerated sequence S, i.e., the sequence [sn, ..., s1].There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Given a complete sequence S and an integer p, create the enumerated sequence formed by cyclically rotating the terms of the sequence p terms: if p is positive, rotation will be to the right; if p is negative, S is cyclically rotated -p terms to the left; if p is zero nothing happens.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Given a complete enumerated sequence S whose terms belong to a structure on which lt and eq are defined, create the enumerated sequence formed by (quick-)sorting the terms of S into increasing order.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Given a complete enumerated sequence S and a comparison function C which compares elements of S, create the enumerated sequence formed by sorting the terms of S into increasing order with respect to C. The comparison function C must take two arguments and return an integer less than, equal to, or greater than 0 according to whether the first argument is less than, equal to, or greater than the second argument (e.g.: func<x, y | x - y>).There are three versions of this: a procedure, where S is replaced by the new sequence, a procedure, where S is replaced by the new sequence and the corresponding permutation p is set, and a function, which returns the new sequence and the corresponding permutation. The procedural version takes a reference ~S to S as an argument. Note that the procedural version is much more efficient since the sequence S will not be copied.
Given a complete enumerated sequence S, sorts it in place and simultaneously sorts T in the same order. That is, whenever the sorting process would swap the two elements S[i] and S[j] then the two elements T[i] and T[j] are also swapped.
Create the sequence which is the same as the enumerated sequence S but with the i-th term of S undefined; i may be bigger than #S, but i≤0 produces an error.There are two versions of this: a procedure, where S is replaced by the new sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Given a sequence S with universe U and a structure V which contains U, construct a sequence 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 sequence, and a function, which returns the new sequence. The procedural version takes a reference ~S to S as an argument.
Note that the procedural version is much more efficient since the sequence S will not be copied.
Given a sequence S with universe U and a structure V which contains U, attempt to construct a sequence T which consists of the elements of S coerced into V; if successful, return true and T, otherwise return false.
The Farey series Fn of degree n consists of all rational numbers with denominator less than or equal to n, in order of magnitude. Since we will need numerator and denominator often, we first abbreviate those functions.
> D := Denominator; > N := Numerator;The first method calculates the entries in order. It uses the fact that for any three consecutive Farey fractions (p)/(q), (p')/(q'), (p")/(q") of degree n: p"=⌊((q + n)/q') ⌋p' - p, q"=⌊((q + n)/q') ⌋q' - q.
> farey := function(n) > f := [ RationalField() | 0, 1/n ]; > p := 0; > q := 1; > while p/q lt 1 do > p := ( D(f[#f-1]) + n) div D(f[#f]) * N(f[#f]) - N(f[#f-1]); > q := ( D(f[#f-1]) + n) div D(f[#f]) * D(f[#f]) - D(f[#f-1]); > Append(~f, p/q); > end while; > return f; > end function;The second method calculates the Farey series recursively. It uses the property that Fn may be obtained from Fn - 1 by inserting a new fraction (namely (p + p')/(q + q')) between any two consecutive rationals (p)/(q) and (p')/(q') in Fn - 1 for which q + q' equals n.
> function farey(n) > if n eq 1 then > return [RationalField() | 0, 1 ]; > else > f := farey(n-1); > i := 0; > while i lt #f-1 do > i +:= 1; > if D(f[i]) + D(f[i+1]) eq n then > Insert( ~f, i+1, (N(f[i]) + N(f[i+1]))/(D(f[i]) + D(f[i+1]))); > end if; > end while; > return f; > end if; > end function;The third method is very straightforward, and uses Sort and Setseq (defined above).
> farey := func< n |
> Sort(Setseq({ a/b : a in { 0..n }, b in { 1..n } | a le b }))>;
> farey(6);
[ 0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1 ]
The enumerated sequence formed by concatenating the terms of S with the terms of T, i.e. the sequence [s1, ..., sn, t1, ..., tm].If the universes of S and T are different, an attempt to find a common overstructure is made; if this fails an error results (see the Introduction).
Mutation assignment: change S to be the concatenation of S and T. Functionally equivalent to S := S cat T.If the universes of S and T are different, an attempt to find a common overstructure is made; if this fails an error results (see the Introduction).
Given a complete non-empty sequence S as well as an integer p that divides the length n of S, construct the sequence whose terms are the sequences formed by taking p terms of S at a time.
Given a complete non-empty sequence S as well as a complete sequence of positive integers P, such that the sum of the entries of P equals the length of S, construct the sequence whose terms are the sequences formed by taking P[i] terms of S, for i=1, ..., #P.
Given a set S, construct a sequence whose terms are the elements of S taken in some arbitrary order.
Given a sequence S, create a set whose elements are the distinct terms of S.
Given a rational number r, this function returns a sequence of different integers di such that r=∑1/di [Bee93].
> egyptian := function(r)
> n := Numerator(r);
> d := Denominator(r);
> s := [d : i in [1..n]];
> t := { d };
> i := 2;
> while i le #s do
> c := s[i];
> if c in t then
> Remove(~s, i);
> s cat:= [c+1, c*(c+1)];
> else
> t join:= { c };
> i := i+1;
> end if;
> end while;
> return s;
> end function;
Note that the result may be rather larger than necessary:
> e := egyptian(11/13); > // Check the result! > &+[1/d : d in e]; 11/13 > #e; 2047 > #IntegerToString(Maximum(e)); 1158while instead of this sequence of 2047 integers, the biggest of the entries having 1158 decimal digits, the following equation also holds: (1/3) + (1/4) + (1/6) + (1/12) + (1/78)=(11/13).
The following operations work pointwise on sequences of booleans of equal length.
The sequence whose ith entry is the logical and of the ith entries of S and T. The result is placed in S if it is given by reference (~).
The sequence whose ith entry is the logical or of the ith entries of S and T. The result is placed in S if it is given by reference.
The sequence whose ith entry is the logical xor of the ith entries of S and T. The result is placed in S if it is given by reference.
The sequence whose ith entry is the logical not of the ith entry of S. The result is placed in S if it is given by reference.