Editing Sequence
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
− | A '''sequence''', '''list''', or '''stream''' is a fundamental concept in mathematics and computer science. It is an entity that contains | + | A '''sequence''', '''list''', or '''stream''' is a fundamental concept in mathematics and computer science. It is an entity that contains countably many other entities, ordered and regarded as a whole. |
==Definitions== | ==Definitions== | ||
Line 8: | Line 8: | ||
If the set from which the elements of a sequence are taken is finite, and the sequence itself is finite, the sequence is also a [[string]]. Sequences, however, can also be infinite and have infinitely many different values for their elements; an example is the Fibonacci sequence. | If the set from which the elements of a sequence are taken is finite, and the sequence itself is finite, the sequence is also a [[string]]. Sequences, however, can also be infinite and have infinitely many different values for their elements; an example is the Fibonacci sequence. | ||
− | While in theory, then, a sequence, list, or stream is merely countably many individual values regarded as a whole, the terms ''list'' and ''stream'' often carry the connotations that they do not support random access efficiently, or perhaps at all. Hence, in certain programming languages, a sequence allowing efficient random access is stored and referred to as an [[array]], a sequence supporting only sequential access is stored as a [[linked list]] but often simply referred to as a ''list'', and a | + | While in theory, then, a sequence, list, or stream is merely countably many individual values regarded as a whole, the terms ''list'' and ''stream'' often carry the connotations that they do not support random access efficiently, or perhaps at all. Hence, in certain programming languages, a sequence allowing efficient random access is stored and referred to as an [[array]], a sequence supporting only sequential access is stored as a [[linked list]] but often simply referred to as a ''list'', and a sequence in which not all the elements might be available right away, such as the sequence of bytes representing standard input, typed on the terminal, is considered a ''stream''. (In a lazy language, such as Haskell, the distinction between the latter two is lost.) We shall assume that the data structure used to represent a sequence is the most appropriate one for the job whenever we discuss algorithms involving sequences. |
We shall usually write sequences as their terms in order, separated by commas, and enclosed by square brackets, ''e.g.'', <math>[x, y, z, ...]</math> where <math>x</math> is the first element, <math>y</math> is the second, and so on. The empty sequence is denoted <math>[\,]</math>. | We shall usually write sequences as their terms in order, separated by commas, and enclosed by square brackets, ''e.g.'', <math>[x, y, z, ...]</math> where <math>x</math> is the first element, <math>y</math> is the second, and so on. The empty sequence is denoted <math>[\,]</math>. | ||
− | A sequence over a totally ordered set is said to be ''' | + | A sequence over a totally ordered set is said to be '''nondecreasing''' if no element is less than the element preceding it (if any). If every element is greater than the element preceding it (unless no such element exists), then the sequence is said to be '''strictly increasing'''. The term '''increasing''' could mean either ''nondecreasing'' or ''strictly increasing'' depending on context, and should usually be avoided for the sake of clarity. The terms '''nonincreasing''' and '''strictly decreasing''' are defined analogously. |
− | The terms '''prefix''', '''suffix''', and '''concatenation''', while strictly applied to [[string]]s, may also be defined and used analogously for sequences, simply for lack of better terms. Note that any suffix of an infinite sequence is infinite. Also, | + | The terms '''prefix''', '''suffix''', and '''concatenation''', while strictly applied to [[string]]s, may also be defined and used analogously for sequences, simply for lack of better terms. Note that any suffix of an infinite sequence is infinite. Also, concatenating two sequences is meaningless if the first is infinite. |
The term '''subsequence''' is not however defined analogously to ''substring''. A subsequence is a sequence obtained by removing some (possibly none, possibly all, possibly infinitely many) terms from a sequence without permuting the remaining terms. Formally, given a sequence <math>X = [x_1, x_2, x_3, ...]</math>, to any strictly increasing sequence <math>[i_1, i_2, i_3, ...]</math> of natural numbers not exceeding the size of <math>X</math>, there corresponds a subsequence <math>[x_{i_1}, x_{i_2}, x_{i_3}, ...]</math> of <math>X</math>. A subsequence of an infinite sequence may be either finite or infinite. | The term '''subsequence''' is not however defined analogously to ''substring''. A subsequence is a sequence obtained by removing some (possibly none, possibly all, possibly infinitely many) terms from a sequence without permuting the remaining terms. Formally, given a sequence <math>X = [x_1, x_2, x_3, ...]</math>, to any strictly increasing sequence <math>[i_1, i_2, i_3, ...]</math> of natural numbers not exceeding the size of <math>X</math>, there corresponds a subsequence <math>[x_{i_1}, x_{i_2}, x_{i_3}, ...]</math> of <math>X</math>. A subsequence of an infinite sequence may be either finite or infinite. |