Operators on Sequences

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.

Access Functions

# S : SeqEnum -> RngIntElt

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.

Parent(S) : SeqEnum -> Str

Returns the parent structure for a sequence S, that is, the structure consisting of all (enumerated) sequences over the universe of S.

Universe(S) : SeqEnum -> Str

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.

S[i] : SeqEnum, RngIntElt -> Elt

The i-th term s_i 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 [s₁, ..., s_n, s_{n + 1}, ..., s_{i - 1}, x] replaces S, where s_{n + 1}, ..., s_{i - 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.

Selection Operators on Enumerated Sequences

Here, S denotes an enumerated sequence [s₁, ..., s_n]. Further, i and j are integers or multi-indices (see Introduction).

S[I] : SeqEnum, [RngIntElt] -> SeqEnum

The sequence [s_i1, ..., s_ir] 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.

Minimum(S) : SeqEnum -> Elt, RngIntElt

Min(S) : SeqEnum -> Elt, RngIntElt

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].

Maximum(S) : SeqEnum -> Elt, RngIntElt

Max(S) : SeqEnum -> Elt, RngIntElt

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].

Index(S, x) : SeqEnum, Elt -> RngIntElt

Index(S, x, f) : SeqEnum, Elt, RngIntElt -> RngIntElt

Position(S, x) : SeqEnum, Elt -> RngIntElt

Position(S, x, f) : SeqEnum, Elt, RngIntElt -> RngIntElt

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.

Representative(R) : SeqEnum -> Elt

Rep(R) : SeqEnum -> Elt

An (arbitrary) element chosen from the enumerated sequence R

Random(R) : SeqEnum -> Elt

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.

Explode(R) : SeqEnum -> List

Given an enumerated sequence R of length r this function returns the r entries of the sequence (in order).

Eltseq(R) : SeqEnum -> SeqEnum

The enumerated sequence R itself. This function is just included for completeness.

Modifying Enumerated Sequences

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).

Append(~S, x) : SeqEnum, Elt ->

Append(S, x) : SeqEnum, Elt -> SeqEnum

Create an enumerated sequence by adding the object x to the end of S, i.e., the enumerated sequence [s₁, ... s_n, 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.

Exclude(~S, x) : SeqEnum, Elt ->

Exclude(S, x) : SeqEnum, Elt -> SeqEnum

Create an enumerated sequence obtained by removing the first occurrence of the object x from S, i.e., the sequence [s₁, ... s_{i - 1}, s_{i + 1}, ..., s_n], where s_i 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.

Include(~S, x) : SeqEnum, Elt ->

Include(S, x) : SeqEnum, Elt -> SeqEnum

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 [s₁, ..., s_n, 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.

Insert(~S, i, x) : SeqEnum, RngIntElt, Elt ->

Insert(S, i, x) : SeqEnum, RngIntElt, Elt -> SeqEnum

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 [s₁, ... s_{i - 1}, x, s_i, ..., s_n]. 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.

Insert(~S, k, m, T) : SeqEnum, RngIntElt, RngIntElt, SeqEnum ->

Insert(S, k, m, T) : SeqEnum, RngIntElt, RngIntElt, SeqEnum -> SeqEnum

Create the sequence [s₁, ..., s_{k - 1}, t₁, ..., t_l, s_{m + 1}, ..., s_n]. 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 s_k. If k > n, then the sequence [s₁, ..., s_n, s_{n + 1}, ..., s_{k - 1}, t₁, ..., t_l] is created, where s_{n + 1}, ..., s_{k - 1} are all undefined. In the case where T is the empty sequence, terms s_k, ..., s_m 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.

Prune(~S) : SeqEnum ->

Prune(S) : SeqEnum -> SeqEnum

Create the enumerated sequence formed by removing the last term of the sequence S, i.e., the sequence [s₁, ..., s_{n - 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.

Remove(~S, i) : SeqEnum, RngIntElt ->

Remove(S, i) : SeqEnum, RngIntElt -> SeqEnum

Create the enumerated sequence formed by removing the i-th term from S, i.e., the sequence [s₁, ... s_{i - 1}, s_{i + 1}, ..., s_n]. 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.

Reverse(~S) : SeqEnum ->

Reverse(S) : SeqEnum -> SeqEnum

Create the enumerated sequence formed by reversing the order of the terms in the complete enumerated sequence S, i.e., the sequence [s_n, ..., 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.

Rotate(~S, p) : SeqEnum, RngIntElt ->

Rotate(S, p) : SeqEnum, RngIntElt -> SeqEnum

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.

Sort(~S) : SeqEnum ->

Sort(S) : SeqEnum -> SeqEnum

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.

Sort(~S, C) : SeqEnum, UserProgram ->

Sort(~S, C, ~p) : SeqEnum, UserProgram, GrpPermElt ->

Sort(S, C) : SeqEnum, UserProgram -> SeqEnum

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.

ParallelSort(~S, ~T) : SeqEnum, SeqEnum ->

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.

Undefine(~S, i) : SeqEnum, RngIntElt ->

Undefine(S, i) : SeqEnum, RngIntElt -> SeqEnum

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.

ChangeUniverse(S, V) : SeqEnum, Str ->

ChangeUniverse(S, V) : SeqEnum, Str -> SeqEnum

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.

CanChangeUniverse(S, V) : SeqEnum, Str -> Bool, SeqEnum

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.

> D := Denominator;
> N := Numerator;

> 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;

> 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;

> 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 ]

> 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;

> e := egyptian(11/13);
> // Check the result!
> &+[1/d : d in e];
11/13
> #e;
2047
> #IntegerToString(Maximum(e));
1158