Алгоритмы работы с множествами

Алгоритмы работы с множествами

 

Множества

 

 

Определение 1. Под множеством X понимается любая совокупность определенных и различимых между собой объектов. Эти объекты называются элементами множества X.

 

Наиболее  простая форма задания множества - перечисление его элементов, например А={4, 7, 13} (множество А состоит из трёх элементов - целых чисел 4, 7, 13).

Другая часто применяемая форма  задания - указание свойств элементов  множества, например A = {x| x^2 ≤ 4} - множество  чисел х, удовлетворяющих указанному условию. 
 
Множества обычно обозначаются большими буквами А, В, С,….X, а их элементы - малыми: а, в, с,… Запись а ∈ X (читается: а принадлежит X) или X ∋ a (читается: X содержит а) означает, что а является элементом множества X.

Пустое множество обозначается значком Ø. 

Определение 2. Множества, состоящие из определённого конечного числа предметов, называются конечными.

Определение 3. Множества, количество элементов которых пересчитать невозможно, называются бесконечными.

Определение 4. Мощность множества (для конечного множества)- это число элементов, из которого множество состоит.

Определение 5. Если каждый элемент множества В является также элементом множества А, множество В называется подмножеством множества А (обозначение - B ⊆ A или A ⊇ B). Эта зависимость между множествами называется  включением.

  
Каждое множество является своим подмножеством (это самое "широкое" подмножество множества). Пустое множество является подмножеством любого множества (это самое "узкое" подмножество). Т.е. для любого множества  A место включения:  А  и  А  А .

 

Любое другое подмножество множества  А содержит хотя бы один элемент  множества А, но не все его элементы. Такие подмножества называются истинными, или собственными подмножествами.

Для истинных подмножеств множества  А применяется обозначение B ⊂ A или A ⊃ B. Если одновременно B ⊆ A и A ⊆ B, т.е каждый элемент множества В принадлежит А, и в то же время каждый элемент А принадлежит В, то А и В, очевидно, состоят из одних и тех же элементов и, следовательно, совпадают. В этом случае применяется знак равенства множеств: A = B.

(Символы ∈, ∋, ⊂, ⊃, ⊆, ⊇ называются символами включения).

 

Здесь и далее будем работать только с конечными множествами.

 

Битовая шкала

 

Множество как математический объект очень часто используется в программах, и для его машинного представления имеется ряд способов. Чаще всего используется два: битовые шкалы и списки. Рассмотрим первый – шкалы (используется только для конечных множеств).

 

Пусть - универсальное непустое конечное множество. Всякому множеству A ⊆ X можно однозначным образом поставить в соответствие битову шкалу (n-разрядный двоичный вектор) – (a₁, a₂, …,a_n), каждый i-ый разряд которого определяется так:

Битовая шкала характеризует принадлежность элемента из X множеству A, поэтому ее также называют характеристическим вектором множества A ⊆ X.

 

Существует 2ⁿ различных n-разрядных двоичных векторов, что совпадает с числом различных подмножеств n-элементного множества X.

 

Пример 1. Пусть заданы , , и . Тогда битовые шкалы множеств A,B,С ⊆ X имеют вид, показанный в таблице.

 

Множество	Битовая шкала
A	0	1	1	0	0
B	0	0	0	0	0
C	1	1	1	1	0

 

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

 

 

Операции над множествами и  их реализации битовыми шкалами

 

Дополнение  множества A есть следующее множество:

.

Тогда битовая шкала (b₁, b₂, …,b_n) множества определяется путем инвертирования всех разрядов шкалы (a₁, a₂, …,a_n):

               

 

Объединение (сумма ) множеств  А и В ( пишется  А В ) есть множество элементов, каждый из которых принадлежит либо А , либо В. Таким образом,  x А В  тогда и только тогда, когда либо  x А ,  либо  x В .  

Пусть множествам A,B соответствуют шкалы (a₁, a₂, …,a_n), (b₁, b₂, …,b_n). Тогда битовая шкала (c₁, c₂, …,c_n) множества C определяется по правилу:

 

Где - операция логического ИЛИ. Это правило можно записать также следующим образом:

Пересечение множеств  А и В ( пишется  А В , рис.2 ) есть множество элементов, каждый из которых принадлежит и А , и В . Таким образом,  x А В  тогда и только тогда, когда   x А  и  x В.

Если множествам A,B соответствуют шкалы (a₁, a₂, …,a_n), (b₁, b₂, …,b_n). То битовая шкала (c₁, c₂, …,c_n) множества C определяется по правилу:

 

где - операция логического И. Это правило можно записать также следующим образом:

 

 

Разность множеств А и В ( пишется  А \ В   или А – В , рис.3 ) есть множество элементов, которые принадлежат множеству А , но не принадлежат множеству В. Это множество называется также дополнением множества В относительно множества А.

 

Битовая шкала (c₁, c₂, …,c_n) множества C=A\B определяется по правилу:

 

 

Симметричная разность множеств А и В ( пишется  А В или А В  ) есть множество, которое содержит все элементы из A, не принадлежащие множеству B, и все элементы из B, не принадлежащие множеству A: 

 

Битовая шкала (c₁, c₂, …,c_n) множества C=A B определяется по правилу:

 

Расстояние между множествами

 

При решении некоторых задач  требуется определить “близость” заданного множества к некоторому другому множеству (например, выполняющему роль эталона). Для этого используется специальное расстояние между множествами. 

Расстоянием Хемминга между множествами A,B ⊆ X называется число равное мощности (числу элементов) множества А В:

где (c₁, c₂, …,c_n)-битовая шкала множества C=A B, которая определяется по правилу:

Таким образом, расстояние Хемминга показывает количество разрядов, в которых различаются  битовые шкалы.

 

Замечание. Если мощность универсального множества очень велика, а подмножества A,B ⊆ X не очень велики, то применение битовых шкал не является эффективным с точки зрения объема используемой памяти. В этом случае необходимо применять списки.

 

Задача на работу с множествами (проверка принадлежности и вычисление расстояния по Хеммингу)

Задача о  почтовом индексе. Для написания цифр почтового индекса используют множество X из 9 элементов, которые обозначены буквами на рис. 1, сами цифры изображены на рис. 2. Будем считать, что элементы перечисляются в следующем порядке: . Необходимо записать множества A_k (k=0,…,9) каждой из десяти цифр (их графического изображения), для этого см. рис. 2 и соответствующие им битовые шкалы. Например, соответствует битовая шкала (1,1,0,1,0, 1,0,1,1).

 

 

 

 

 
                                                 Рис.1

Рис.2.

Разработать программу, которая позволяла бы по X и битовым шкалам множеств A_k выполнять следующие действия:

1. Найти среди A_k пары непересекающихся множеств,

2. Для каждого элемента  x X найти число подмножеств A_k, в которые он входит.

3. Для заданной цифры (с клавиатуры) найти найти наименее близкую цифру (в смысле расстояния Хемминга).

4. Найти среди A_k пару наиболее близких множеств (в смысле расстояния Хемминга).

5. Для заданного почтового индекса  (с клавиатуры) – найти в нем пару наименее близких цифр (в смысле расстояния Хемминга).

 

Генерация всех подмножеств множества

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

 

Формулировка  задачи

Пусть - универсальное конечное множество. Оно имеет 2ⁿ различных подмножеств. Каждое из этих подмножеств A ⊆ X задается битовой шкалой (a₁, a₂, …,a_n), где

Такое представление показывает, что  порождение всех подмножеств множества  можно свести к генерации всех n-разрядных двоичных векторов.

Рассмотрим три самых популярных алгоритма генерации двоичных векторов. В этих алгоритмах двоичные векторы формируются в одномерном массиве B длины n, элементами его являются значения 0 и 1. Величина n>=0 поступает на вход алгоритмов.

Счет в двоичной системе счисления

Наиболее простым методом генерации  всех двоичных векторов B₁,…,B_n является счет в двоичной системе счисления.

Алгоритм 1. Порождение двоичных векторов

1. В качестве начального взять  вектор B=(0,…,0), т.е. для каждого i=1,…,n B[i]=0.

2. Вывести текущее значение вектора B.

3. Если В=(1,…,1), перейти на пункт 6, иначе идти дальше.

4. Найти m, как наибольшее значение I, для которого B[i]=0 (i=1,…,n).

5. Присвоить B[m]=1 и для каждого j=m+1,..,n выполнить B[j]=0. Вернуться к пункту 2.

6.Остановка алгоритма.

Нетрудно убедиться, что данный алгоритм последовательно генерирует двоичные разложения целых чисел 0,1,…, 2^n-1.

Основным недостатком алгоритма  является то, что получаемые соседние двоичные наборы различаются во всех разрядах и соответствуют непересекающимся подмножествам.

Бинарные коды Грея

Рассмотрим другой метод, при котором каждое последующее подмножество получается из предыдущего добавлением или удалением одного элемента.

Данный метод опирается на следующий  факт. Если последовательность B₁,…,Bm содержит все m=2k двоичных векторов длины k, причем B_i отличается от B_i+1 в точности в одном разряде (i=1, .., m-1), то последовательность

    B₁0, B₂0,…,B_m0, B_m1,B_m-11…, B₁1

Содержит все двоичные векторы  длины k+1, причем каждые два соседних вектора отличаются в точности в одном разряде. Получаемая этим способом последовательность векторов B₁,…,Bm, где m=2ⁿ называется бинарным кодом Грея порядка n.

Алгоритм 2. Рекурсивное построение кода Грея.

1. Поместить 0 после каждого двоичного  вектора B_i (i=1,…,m). Получится последовательность

B₁0, B₂0,…,B_m0.

2. Реверсировать последовательность B₁,…,Bm , т.е. изменить порядок их перечисления на обратный. В полученной последовательности после каждого двоичного вектора записать 1. В результате получим последовательность