 |
Алгоритмы генерации множеств
|
|
|
|
Реализация операций над подмножествами заданного универсума U
Пусть универсум U – конечный, и число элементов в нем не превосходит разрядности ЭВМ: мощность | U | < n. Элементы универсума нумеруются: U = { u 1,…, un }. Подмножество А универсума U представляется кодом (машинным словом или битовой шкалой) С, в котором:
где С(i) – это i ‑й разряд кода С.
Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества А. В большинстве ЭВМ для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно.
Если мощность универсума превосходит размер машинного слова, но не очень велика, то для представления множеств используются массивы битовых шкал. В этом случае операции над множествами реализуются с помощью циклов по элементам массива [23].
Генерация всех подмножеств универсума
Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В большинстве компьютеров целые числа представляются кодами в двоичной системе счисления, причем число 2 k – 1 представляется кодом, содержащим k единиц. Таким образом, число 0 является представлением пустого множества 0, число 1 является представлением подмножества, состоящего из первого элемента, и т. д. Следующий тривиальный алгоритм перечисляет все подмножества n ‑элементного множества (представлен в паскале-подобном коде, описание в [23]).
Алгоритм 1.1: Алгоритм генерации всех подмножеств n‑ элементного множества
|
|
|
Вход: n 
0 – мощность множества
Выход: последовательность кодов подмножеств i
for i from 0 to 2n – 1 do
yield i
end for
Обоснование: Алгоритм выдает 2 n различных целых чисел, следовательно, 2 n различных кодов.
С увеличением числа n увеличивается количество двоичных разрядов, необходимых для его представления. Самое большое (из генерируемых) число 2 n ‑1 требует для своего представления ровно n разрядов. Таким образом, все подмножества генерируются, причем ровно по одному разу.
Во многих переборных задачах требуется рассмотреть все подмножества некоторого множества и найти среди них то, которое удовлетворяет заданному условию. При этом проверка условия часто может быть весьма трудоемкой и зависеть от состава элементов очередного рассматриваемого подмножества. В частности, если очередное рассматриваемое подмножество незначительно отличается по набору элементов от предыдущего, то иногда можно воспользоваться результатами оценки элементов, которые рассматривались на предыдущем шаге перебора. В таком случае, если перебирать множества в определенном порядке, можно значительно ускорить работу переборного алгоритма. [5]
Алгоритм построения бинарного кода Грея
Данный алгоритм генерирует последовательность всех подмножеств n ‑элементного множества, причем каждое следующее подмножество получается из предыдущего удалением или добавлением одного элемента.
Алгоритм 1.2: Алгоритм построения бинарного кода Грея Вход: n 0 – мощность множества
Выход: последовательность кодов подмножеств В
В: array [l..n] of 0..1 {битовая шкала для представления подмножеств}
for i from 1 to n do
B[i]: = 0 {инициализация} end for
yield В {пустое множество}
for i from I to 2n – 1 do
p: = Q(i) {определение элемента, подлежащего добавлению или удалению}
B[р]: = 1 – В[р] {добавление или удаление элемента}
yield В {очередное подмножество} end for
|
|
|
proc Q(i) {количество 2 в разложении i на множители + 1} q: = l; j: = i while j четно do
j:=j/2; q: = q + l end while return q end proc
Обоснование
Для n = 1 искомая последовательность кодов суть 0,1. Пусть есть искомая последовательность кодов В 1,…, 
для n = к. Тогда последовательность кодов B 10,…, 0, 1, …. B 11 будет искомой последовательностью для n = к + 1. Действительно, в последовательности B 10,…, 0, 1,…, В 11 имеется 2 k +1 кодов, они все различны и соседние различаются ровно в одном разряде по строению. Именно такое построение и осуществляет данный алгоритм. На нулевом шаге алгоритм выдает правильное подмножество В (пустое). Пусть за первые 2 k – 1 шагов алгоритм выдал последовательность значений В. При этом В [ k + 1] = В [ k + 2] = • • • = В [ n ] = 0. На 2 k ‑ом шаге разряд В [ k + 1] изменяет свое значение с 0 на 1. После этого будет повторена последовательность изменений значений В [1. k ] в обратном порядке, поскольку Q (2 k + m) = Q (2 k – m) для 
Пример 2.4
Таблица 2.5 – Протокол выполнения алгоритма 1.2 для п = 3
| i | Р | В | ||
| 0 | 0 | 0 | ||
| 1 | 1 | 0 | 0 | 1 |
| 2 | 2 | 0 | 1 | 1 |
| 3 | 1 | 0 | 1 | 0 |
| 4 | 3 | 1 | 1 | 0 |
| 5 | 1 | 1 | 1 | 1 |
| 6 | 2 | 1 | 0 | 1 |
| 7 | 1 | 1 | 0 | 0 |
Представление множеств упорядоченными списками
Если универсум очень велик (или бесконечен), а рассматриваемые подмножества универсума не очень велики, то представление с помощью битовых шкал не является эффективным с точки зрения экономии памяти. В этом случае множества обычно представляются списками элементов. Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующий элемент. Весь список представляется указателем на первый элемент.
elem = record
i: info; {информационное поле}
n: elem {указатель на следующий элемент} end record
При таком представлении трудоемкость операции 
составит O (n), а трудоемкость операций 
составит О (nm), где n и m – мощности участвующих в операции множеств.
Если элементы в списках упорядочить, например, по возрастанию значения поля i, то трудоемкость всех операций составит О (n). Эффективная реализация операций над множествами, представленными в виде упорядоченных списков, основана на весьма общем алгоритме, известном как алгоритм типа слияния.
1
1 1
1 2 1
13 3 1
14 6 4 1
Рисунок 2.9 – Иллюстрация к алгоритму слияния
|
|
|
В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число сочетаний С (m, n) находится в (m + 1) – м ряду на (n + 1) – м месте.
Генерация подмножеств
Элементы множества {1,…, m } упорядочены. Поэтому каждое n ‑элементное подмножество также можно рассматривать как упорядоченную последовательность. На множестве таких последовательностей естественным образом определяется лексикографический порядок. Следующий простой алгоритм генерирует все n ‑элементные подмножества m ‑элементного множества в лексикографическом порядке.
Алгоритм 1.3. Генерация n ‑элементных подмножеств m ‑элементного множества
Вход: n – мощность подмножества, m – мощность множества, m n > 0.
Выход: последовательность всех n ‑элементных подмножеств m ‑элементного множества в лексикографическом порядке.
for i from 1 to m do
A[i]: = i {инициализация исходного множества} end for
if m = n then
yield A [1..n] {единственное подмножество} exit end if
p: = n {p – номер первого изменяемого элемента} while p 1 do
yield A [1..n] {очередное подмножество в первых n элементах массива А} if А[i] = m then
р: = р – 1 {нельзя увеличить последний элемент} else
р:=n {можно увеличить последний элемент} end if if p 1 then
for i from n downto p do
А[i]: = А[р]+i‑р+1 {увеличение элементов} end for end if end while
Заметим, что в искомой последовательности n ‑элементиых подмножеств (каждое из которых является возрастающей последовательностью n чисел из диапазона l.. m) вслед за последовательностью (ai,…, an) следует последовательность
(b 1,…, bn) = (а 1…, ap -1, ар + 1, ар + 2,…, ар + n-р +1), где р – максимальный индекс, для которого bn = ар + n - р + 1 
m. Другими словами, следующая последовательность получается из предыдущей заменой некоторого количества элементов в хвосте последовательности на идущие подряд целые числа, но так, чтобы последний элемент не превосходил n, а первый изменяемый элемент был на 1 больше, чем соответствующий элемент в предыдущей последовательности. Таким образом, индекс р, начиная с которого следует изменить «хвост последовательности», определяется по значению элемента А [ n ]. Если А [ n ] < m, то следует изменять только А [ n ], и при этом р: = n. Если же уже А (n) = m, то нужно уменьшать индекс р: = р – 1, увеличивая длину изменяемого хвоста.
|
|
|
|
|
|
