Основы дискретной математики

Пример 2.4

Таблица 2.5 – Протокол выполнения алгоритма 1.2 для п = 3

Представление множеств упорядоченными списками

Если универсум очень велик (или бесконечен), а рассматриваемые подмножества универсума не очень велики, то представление с помощью битовых шкал не является эффективным с точки зрения экономии памяти. В этом случае множества обычно представляются списками элементов. Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующий элемент. Весь список представляется указателем на первый элемент.

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) следует последовательность

(b1,…, bn) = (а1…, ap-1, ар + 1, ар + 2,…, ар + n-р +1), где р – максимальный индекс, для которого bn = ар + n - р + 1 m. Другими словами, следующая последовательность получается из предыдущей заменой некоторого количества элементов в хвосте последовательности на идущие подряд целые числа, но так, чтобы последний элемент не превосходил n, а первый изменяемый элемент был на 1 больше, чем соответствующий элемент в предыдущей последовательности. Таким образом, индекс р, начиная с которого следует изменить «хвост последовательности», определяется по значению элемента А[n]. Если А[n] < m, то следует изменять только А[n], и при этом р: = n. Если же уже А(n) = m, то нужно уменьшать индекс р: =р – 1, увеличивая длину изменяемого хвоста.

2.1.4 Представление множеств в приложениях на Delphi

Тип множество задает неупорядоченную совокупность неповторяющихся объектов. Переменная типа множество – это совокупность объектов из исходного заданного множества – может иметь значение «пусто» (пустое множество). Число элементов исходного множества ограничено – оно не может быть более 256. Для задания элементов множества может использоваться любой порядковый тип, однако порядковые номера элементов множества, т. е. значения функции ord, должны находиться в пределах от 0 до 255. Для задания типа множества используется следующее объявление [22]:

Type <Имя> = set of <тип элементов>;

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

Type A = set of Char; A1 = set of ‘A’.’Z’;

Oper = set of (Plus, Minus, Mult, Divide);

Number = set of Byte; D = set of 1 20;

Для переменных типа множество можно задавать типизированные константы. При этом значения задаются в виде конструктора множества.

 Скачать реферат