Sets and sequences: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(19 intermediate revisions by the same user not shown)
Line 2: Line 2:
[[Category:Background]]
[[Category:Background]]
==Sets and multisets==
==Sets and multisets==
# In a '''set''', each element occurs at most once, that is, no duplications of elements within a set.
# In a '''proper set''' (or '''set''', for short), each element occurs at most once, that is, no duplications of elements within a set.
# In contrast, in a '''multiset''', an element may occur more than once. The '''multiplicity''' of an element in a multiset is the number of its occurrences in that multiset.
# In contrast, in a '''multiset''', an element may occur more than once. The '''multiplicity''' of an element in a multiset is the number of its occurrences in that multiset.


'''Remark:'''
'''Remarks:'''
In computer science, as opposed to math, sets and multisets are usually dynamic, that is, elements may be inserted and removed.
# In computer science, as opposed to math, sets and multisets are usually dynamic, that is, elements may be inserted and removed.
# Uniting two multisets amounts to adding the multiplicities. To intersect two multisets, take the minimum of the multiplicities. (Multi)set difference is realized by subtracting the multiplicities in the subtrahend from the multiplicities in the minuend.
 
== Maximal and minimal sets ==
== Maximal and minimal sets ==


Let <math>\mathcal{S}</math> be a set of (multi)sets.
Let <math>\mathcal{S}</math> be a set of (multi)sets.
# A set <math>S\in\mathcal{S}</math> is '''inclusion-minimal''' (resp., '''inclusion-maximal''') if <math>S'\subsetneq S</math> (resp., <math>S'\supsetneq S</math>) for no <math>S'\in\mathcal{S}\setminus\{S\}</math>.
# A set <math>S\in\mathcal{S}</math> is '''inclusion-minimal''' (resp., '''inclusion-maximal''') in <math>\mathcal{S}</math> if <math>S'\subsetneq S</math> (resp., <math>S'\supsetneq S</math>) for no <math>S'\in\mathcal{S}\setminus\{S\}</math>.
# A set <math>S\in\mathcal{S}</math> is '''cardinality-minimal''' (resp., '''cardinality-maximal''') if <math>|S'|<[S[</math> (resp., <math>|S'|>|S|</math>) for no <math>S'\in\mathcal{S}\setminus\{S\}</math>.
# A set <math>S\in\mathcal{S}</math> is '''cardinality-minimal''' (resp., '''cardinality-maximal''') in <math>\mathcal{S}</math> if <math>|S'|<|S|</math> (resp., <math>|S'|>|S|</math>) for no <math>S'\in\mathcal{S}\setminus\{S\}</math>.


'''Remark:'''
'''Remark:'''
Line 22: Line 23:
# some '''component type''' <math>C</math>, and
# some '''component type''' <math>C</math>, and
# a mapping <math>\pi : \{1,...,n\} \rightarrow C</math>.
# a mapping <math>\pi : \{1,...,n\} \rightarrow C</math>.
We say that <math>1,...,n</math> are the '''positions''' in the sequence (a.k.a. the '''indexes'''). The element <math>\pi (i)</math> of sequence <math>S</math> at position <math>i</math> is denoted by <math>S[i]</math>.
We say that <math>1,...,n</math> are the '''positions''' in the sequence (a.k.a. the '''indexes'''). The element <math>\pi (i)</math> of sequence <math>S</math> at position <math>i</math> is denoted by <math>S[i]</math>. The element <math>S[1]</math> is the '''head''' of <math>S</math>, and the element <math>S[n]</math> is the '''tail''' of <math>S</math>.


Consider a comparison <math>c</math> on <math>C</math>, as introduced above. Then a sequence <math>S</math> of length <math>n</math> is '''sorted''' with respect to <math>c</math>, if <math>S[i] \le S[i+1]</math> for all <math>i \in \{1,...,n-1\}</math>.
Consider a [[Genericity#Comparison|comparison]] <math>c</math> on <math>C</math>. Then a sequence <math>S</math> of length <math>n</math> is '''sorted''' with respect to <math>c</math>, if <math>S[i] \le S[i+1]</math> for all <math>i \in \{1,...,n-1\}</math>.


'''Remarks:'''
'''Remarks:'''
Line 30: Line 31:
# Like [[#Sets and multisets|sets and multisets]], sequences are dynamic.
# Like [[#Sets and multisets|sets and multisets]], sequences are dynamic.


== Singleton, pair, triple ==
== Singleton, pair, triple, quadruple ==


A set, multiset or sequence with only one, two or three elements is called a '''singleton''', '''pair''' and '''triple''', respectively.
A set, multiset or sequence with only one, two, three, or four elements is called a '''singleton''', '''pair''', '''triple''', and '''quadruple''', respectively.


== Stacks and queues ==
== Stacks and queues ==


# A '''stack''' (a.k.a. '''LIFO queue''', LIFO = last-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the beginning (the '''top'''), and no element except for the very first one may be accessed and removed.
# A '''stack''' (a.k.a. '''LIFO queue''', LIFO = last-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted before the head (a.k.a. '''top'''), and no element except for the current head may be accessed and removed.
# A '''queue''' (a.k.a. '''FIFO queue''', FIFO = first-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the end, and no element except for the very first one may be accessed and removed.
# A '''queue''' (a.k.a. '''FIFO queue''', FIFO = first-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the end (that is, after the current tail), and no element except for the head  may be accessed and removed.
 
'''Remark:''' For fast access, an implementation of a FIFO queue should maintain an additional pointer to the tail. To update this pointer after an append, simply move it one step forward in the sequence.


==Maps==
==Maps==
A '''map''' is given by
A '''map''' is given by
# a number <math>n \in \N_{0}</math>, its '''size'''
# a number <math>n \in \N_{0}</math>, its '''size''',
# a '''key type''' <math>\mathcal{K}</math> and a '''value type''' <math>\mathcal{V}</math>,
# a '''key type''' <math>\mathcal{K}</math> and a '''value type''' <math>\mathcal{V}</math>,
# a finite subset <math>K \subseteq \mathcal{K}</math>, the map's '''keys''', and
# a finite subset (a proper set) <math>K \subseteq \mathcal{K}</math>, the map's '''keys''', and
# a mapping <math>K \rightarrow \mathcal{V}</math>, which assigns a value to each key in the map.
# a mapping <math>K \rightarrow \mathcal{V}</math>, which assigns a value to each key in the map.
Like '''sets, multisets and sequences''', maps are dynamic in computer science.


'''Remark:'''
'''Remark:'''
A sequence may also be a map, namely if its component type is <math>\mathcal{K} \times \mathcal{V}</math> and each value of <math>\mathcal{K}</math> occurs at most once.
A sequence may also implement a map, namely if its component type is <math>\mathcal{K} \times \mathcal{V}</math> and each value of <math>\mathcal{K}</math> occurs at most once.
 
Like '''sets, multisets and sequences''', maps are dynamic.


== Partitions ==
== Partitions ==


Let <math>I</math> ba a finite or infinite set of positive integral numbers.
Let <math>I</math> be a finite or infinite set of positive integral numbers.
# A '''partition''' of a finite or infinite set <math>S</math> is a family <math>\{S_i|i\in I\}</math> of subsets of <math>S</math> such that <math> V_i\cap V_j=\emptyset</math> for all <math>i,j\in I</math>, <math>i\neq j</math>, and <math>\bigcup_{i\in I}S_i=S</math>.
# A '''partition''' of a finite or infinite set <math>S</math> is a family <math>\{S_i|i\in I\}</math> of subsets of <math>S</math> such that
# If <math>I</math> is finite, we speak of a <math>k</math>-partition, where <math>k=|I|</math>.
## <math> V_i\cap V_j=\emptyset</math> for all <math>i,j\in I</math>, <math>i\neq j</math>, and
# In particular, if <math>|I|=2</math>, we speak of a bipartition.
## <math>\bigcup_{i\in I}S_i=S</math>.
# If <math>I</math> is finite, we speak of a '''<math>k</math>-partition''', where <math>k=|I|</math>.
# In particular, if <math>|I|=2</math>, we speak of a '''bipartition'''.

Latest revision as of 12:24, 21 May 2015

Sets and multisets

  1. In a proper set (or set, for short), each element occurs at most once, that is, no duplications of elements within a set.
  2. In contrast, in a multiset, an element may occur more than once. The multiplicity of an element in a multiset is the number of its occurrences in that multiset.

Remarks:

  1. In computer science, as opposed to math, sets and multisets are usually dynamic, that is, elements may be inserted and removed.
  2. Uniting two multisets amounts to adding the multiplicities. To intersect two multisets, take the minimum of the multiplicities. (Multi)set difference is realized by subtracting the multiplicities in the subtrahend from the multiplicities in the minuend.

Maximal and minimal sets

Let [math]\displaystyle{ \mathcal{S} }[/math] be a set of (multi)sets.

  1. A set [math]\displaystyle{ S\in\mathcal{S} }[/math] is inclusion-minimal (resp., inclusion-maximal) in [math]\displaystyle{ \mathcal{S} }[/math] if [math]\displaystyle{ S'\subsetneq S }[/math] (resp., [math]\displaystyle{ S'\supsetneq S }[/math]) for no [math]\displaystyle{ S'\in\mathcal{S}\setminus\{S\} }[/math].
  2. A set [math]\displaystyle{ S\in\mathcal{S} }[/math] is cardinality-minimal (resp., cardinality-maximal) in [math]\displaystyle{ \mathcal{S} }[/math] if [math]\displaystyle{ |S'|\lt |S| }[/math] (resp., [math]\displaystyle{ |S'|\gt |S| }[/math]) for no [math]\displaystyle{ S'\in\mathcal{S}\setminus\{S\} }[/math].

Remark: Typically, [math]\displaystyle{ \mathcal{S} }[/math] is given as all subsets of a ground set that fulfill a certain property.

Ordered and sorted sequences

An ordered sequence (or sequence, for short) is given by

  1. a number [math]\displaystyle{ n \in \N_{0} }[/math], its length,
  2. some component type [math]\displaystyle{ C }[/math], and
  3. a mapping [math]\displaystyle{ \pi : \{1,...,n\} \rightarrow C }[/math].

We say that [math]\displaystyle{ 1,...,n }[/math] are the positions in the sequence (a.k.a. the indexes). The element [math]\displaystyle{ \pi (i) }[/math] of sequence [math]\displaystyle{ S }[/math] at position [math]\displaystyle{ i }[/math] is denoted by [math]\displaystyle{ S[i] }[/math]. The element [math]\displaystyle{ S[1] }[/math] is the head of [math]\displaystyle{ S }[/math], and the element [math]\displaystyle{ S[n] }[/math] is the tail of [math]\displaystyle{ S }[/math].

Consider a comparison [math]\displaystyle{ c }[/math] on [math]\displaystyle{ C }[/math]. Then a sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math] is sorted with respect to [math]\displaystyle{ c }[/math], if [math]\displaystyle{ S[i] \le S[i+1] }[/math] for all [math]\displaystyle{ i \in \{1,...,n-1\} }[/math].

Remarks:

  1. Note that the first position is [math]\displaystyle{ 1 }[/math], not [math]\displaystyle{ 0 }[/math], as opposed to array indexes in many popular programming languages such as C, C++, and Java.
  2. Like sets and multisets, sequences are dynamic.

Singleton, pair, triple, quadruple

A set, multiset or sequence with only one, two, three, or four elements is called a singleton, pair, triple, and quadruple, respectively.

Stacks and queues

  1. A stack (a.k.a. LIFO queue, LIFO = last-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted before the head (a.k.a. top), and no element except for the current head may be accessed and removed.
  2. A queue (a.k.a. FIFO queue, FIFO = first-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the end (that is, after the current tail), and no element except for the head may be accessed and removed.

Remark: For fast access, an implementation of a FIFO queue should maintain an additional pointer to the tail. To update this pointer after an append, simply move it one step forward in the sequence.

Maps

A map is given by

  1. a number [math]\displaystyle{ n \in \N_{0} }[/math], its size,
  2. a key type [math]\displaystyle{ \mathcal{K} }[/math] and a value type [math]\displaystyle{ \mathcal{V} }[/math],
  3. a finite subset (a proper set) [math]\displaystyle{ K \subseteq \mathcal{K} }[/math], the map's keys, and
  4. a mapping [math]\displaystyle{ K \rightarrow \mathcal{V} }[/math], which assigns a value to each key in the map.

Like sets, multisets and sequences, maps are dynamic in computer science.

Remark: A sequence may also implement a map, namely if its component type is [math]\displaystyle{ \mathcal{K} \times \mathcal{V} }[/math] and each value of [math]\displaystyle{ \mathcal{K} }[/math] occurs at most once.

Partitions

Let [math]\displaystyle{ I }[/math] be a finite or infinite set of positive integral numbers.

  1. A partition of a finite or infinite set [math]\displaystyle{ S }[/math] is a family [math]\displaystyle{ \{S_i|i\in I\} }[/math] of subsets of [math]\displaystyle{ S }[/math] such that
    1. [math]\displaystyle{ V_i\cap V_j=\emptyset }[/math] for all [math]\displaystyle{ i,j\in I }[/math], [math]\displaystyle{ i\neq j }[/math], and
    2. [math]\displaystyle{ \bigcup_{i\in I}S_i=S }[/math].
  2. If [math]\displaystyle{ I }[/math] is finite, we speak of a [math]\displaystyle{ k }[/math]-partition, where [math]\displaystyle{ k=|I| }[/math].
  3. In particular, if [math]\displaystyle{ |I|=2 }[/math], we speak of a bipartition.