Операции над множествами

Описание

Описание типа множества имеет вид:

type <имя типа> = set of <базовый тип>;

Здесь <имя типа> - идентификатор; <базовый тип> - один из скалярных типов, кроме вещественного. Базовый тип задаётся диапазоном или перечислением. Из стандартных типов в качестве базового типа множества могут быть указаны типы byte, char и boolean. Базовый тип вводится либо через предварительное определение в разделе описаний программы, либо с помощью прямого указания после слов set of в описании типа множества, например:

type letter = 'a'.. 'z'; // Описание ограниченного типа letter

type SL = set of letter; // Описание множественного типа SL с базовым типом letter

type SLR = set of ‘a’.. 'z'; // Прямое включение определения базового типа 'a.. 'z' в описание множественного типа SLR

Если в программе используются переменные, значениями которых являются множества, то эти переменные описываются обычным образом:

type intset = set of byte;

var m1, m2: intset; // Переменные описаны через указание принадлежности ранее определённому типу

var m3: set of 1..20; // Определение типа переменной непосредственно включено в её описание

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

[ ] – пустое множество;

[1, 3, 5.. 12] – множество, содержащее элементы 1, 3, 5, 6,.. 12;
['a'.. 'p', 'u', 'z'] – множество, состоящее из перечисленных символов типа char.

Элементы типа множества могут задаваться в виде выражений, например: [2+4, 3 * 2]. Выражения должны иметь значения из заданного базисного множества порядкового типа. Область значений переменной множественного типа представляет собой набор всевозможных подмножеств, образованных из элементов базового типа.

В отличие от перечислений нельзя говорить о первом, втором и т.п. элементах множества, поскольку для множеств понятие упорядоченности не имеет смысла. Если множество содержит всего три элемента, то общее количество возможных комбинаций составляет 2 * 2 * 2 = 8. Зарезервированное слово set способно определять множество размерностью до 256 элементов, т.е. 1,1579208923731619542357098500869e+77 вариантов. На практике такое количество вариантов никогда не понадобится. В частности, разработчики Delphi рекомендуют использовать множество с количеством элементов не более 16.

Над переменными множественного типа могут выполняться те же операции, что и над обычными множествами:

1. Объединение (+);
2. Пересечение (*);
3. Разность (-).

Кроме того, определённые операции проверки принадлежности элемента множеству (in), проверки тождественности множеств (=), нетождественности, множеств (<>), определения принадлежности (вложенности) множеств (>= или <=). Примеры:

1. [1, 2, 4] = [1, 4, 2] // Результат True
2. ['a'.. 'z'] = ['a'.. 'p'] // Результат False
3. [1, 2, 5, 6] <> [1, 2] // Результат True
4. [‘a’, ‘b’, ‘c’] <= [‘a’.. ‘z’] // Результат True
5. [‘a’.. ‘k’] >= [‘a’.. 'z'] // Результат False
6. [1, 2, 3] + [1, 4, 5] // Результат [1, 2, 3, 4, 5]
7. [1, 2, 3] * [1, 3, 4, 5] // Результат [1, 3]
8. [1, 3, 4, 5] – [1, 4, 6] // Результат [3, 5]

Операция in позволяет определить, принадлежит ли элемент множеству или нет. Первым операндом, стоящим слева от слова in, является выражение базового типа. Второй операнд, стоящий справа от слова in, должен иметь множественный тип, например:

a in [a, b, c, d] // Результат True
2 * 4 in [0.. 4, 7.. 10] // Результат True
‘a’ + ‘b’ in [‘ab’, ‘cd’, ‘ef’] // Результат True
5 in [1 * 2, 4, 5] // Результат True
5 in [2, 4, 6, 8] // Результат False

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

Операция in позволяет проводить эффективно сложные проверки условий. Например, вместо:

(c >= '0') and (c <= '9') or (c >= 'a') and (c <='z');

Проще записать:

c in [‘0’.. ‘9’, ‘a’.. 'z'];

Причём последняя конструкция будет, как правило, более эффективной.

Операции (=) и (<>) позволяют проверить, равны ли два множества или нет. С помощью операций (>=) и (<=) можно определить, является ли одно множество подмножеством другого. Пример:

[red, white] = [red, green] // Результат False

[1] <= [0.. 4] // Результат True

Замечания:
1. Пустое множество [ ] является подмножеством любого другого множества независимо от базового типа его элементов.
2. Множества-операнды могут иметь непересекающиеся базовые типы. Располагая, например, множествами A: set of 1.. 99 и B: set of 100.. 150, можно в результате объединения A+B получить новое множество с базовым типом 1.. 150.
3. Следует различать конструктор множества [X.. Y] и отрезок порядкового типа X.. Y. При X > Y в первом случае речь идёт о пустом множестве, а во втором компилятор выдаст ошибку. Пример:

['a', 'b'] = ['b'.. 'a'] // Результат False

При проверке на подмножество выполняется тест на «меньше или равно», а не только проверка на собственное подмножество, т.е без «равно». Операции (<) и (>) не предусмотрены, поэтому при необходимости проверку на собственное подмножество для множеств A и B можно провести следующим образом:

(A <= B) and (A >= B) или (A >= B) and (A <> B)

Для задания правильного порядка выполнения операций следует учитывать принятый порядок старшинства (приоритета) операций над множествами: пересечение (*) имеет тот же приоритет, что и арифметические операции умножения и деления; объединение (+) и разность (-) занимают следующий, более низкий уровень приоритета, аналогично арифметическим операциям сложения и вычитания; на самом нижнем уровне находятся операции сравнения множеств (=, <>, <=, >=) и проверки принадлежности элемента множеству (in). Операции одного приоритета выполняются слева направо. Для изменения порядка выполнения операций используются круглые скобки.

Дата добавления: 2014-12-25