Комбинаторные алгоритмы для программистов



             

Множества и мультимножества


Не существует формального определения множества; считается что это понятие первичное и не определяется. Так, можно говорить, что множество есть объединение различных элементов, но при этом мы оставляем неопределяемыми понятия "объединение" и "элементы". Дадим следующее определение множеству: множество - это неупорядоченная совокупность различных объектов или структура данных, используемая для представления множества. Мультимножество есть объединение не обязательно различных элементов; его можно считать множеством, в котором каждому элементу поставлено в соответствие положительное целое число, называемое кратностью.

Конечное множество

S
будем записывать в следующем виде:

 S = \{ s_1,s_2,\ldots,s_n \},

где

s_1,s_2,\ldots,s_n
- элементы
S
, обязательно различные! Мощность множества
S
обозначается как
\left| S\right|
, для выписанного выше множества мощность записывается так
\left| S \right| = n
. Если
S
- конечное мультимножество, то будем записывать его в следующем виде:

S=\{\uns{s_1,s_1,\ldots,s_1}{m_1\text{раз}},\uns{s_2,s_2,\ldots,s_2}{m_2\text{ раз}}, \uns{s_3,s_3,\ldots,s_3}{m_3\text{ раз}}\} = \{ m_1 \bullet s_1, m_2 \bullet s_2,\ldots,m_n \bullet s_n \}.

Здесь все

s_i
различны и
m_i
- кратность элемента
s_i
. В этом случае мощность
S
равна

\left| S \right| = \sum\limits_{i = 1}^n {m_i }.

Наиболее общими операциями на множествах и мультимножествах являются операции объединения и пересечения. Для множеств эти операции будем обозначать

\cup
и
\cap
, а для мультимножеств -
\mathop \cup \limits^ +
и
\mathop \cap \limits^ +
. Последовательное и связанное представление последовательностей можно использовать для множеств и мультимножеств очевидным способом. Индуцируя искусственный порядок элементов множества или используя собственный порядок, если он существует, можно рассматривать множество как последовательность. Аналогично, как последовательность можно рассматривать и мультимножество, или, для того чтобы сэкономить место, его можно рассматривать как последовательность пар, каждая из которых состоит из элемента и его кратности.

Как и для последовательностей, наилучший метод представления множеств или мультимножеств существенно зависит от операций, которые выполняются над ними. Предположим, например, что имеем дело с непересекающимися подмножествами множества

S = \{ s_1,s_2,\ldots,s_n \}
и что над ними необходимо выполнить две следующие операции: объединение двух множеств и отыскание подмножества, содержащего данное
s_i
.


Содержание    Вперед