var <имя_множества>: set of <тип_элементов_множества>;

var s1: set of char; {множество из 256-ти элементов}
 s2: set of 'a'..'z','A'..'Z'; {множество из 52-х элементов}
 s3: set of 0..10; {множество из 11-ти элементов}
 s4: set of boolean; {множество из 2-х элементов}

[<список_элементов>]

if c in ['a','e','i','o','u'] 
 then writeln('Гласная буква');
if set1 < [k*2+1..n,13] then set1:=[];

<имя_константы> : set of <тип_элементов> =[<список_элементов>];

type cipher = set of '0'..'9';
const odds: cipher = ['1','3','5','7','9'];
 vowels: set of 'a'..'z' = ['a','o','e','u','i'];
Все теоретико-множественные операции реализованы и в языке 
Pascal:





1) Пересечение двух множеств s1 и s2:
s:=s1*s2;

2) Объединение двух множеств s1 и s2: 
s:=s1+s2;

3) Разность двух множеств s1 и s2 (все элементы, которые 
принадлежат множеству s1 и одновременно не 
принадлежат множеству s2)1):
s:=s1-s2;

4) Проверка принадлежности элемента el множеству s (результат этой 
операции имеет тип boolean):
el in s

5) Обозначение для пустого множества: 
[]

6) Создание множества из списка элементов: 

s:=[e1,_,eN];


7) Проверка двух множеств на равенство или 
строгое включение (результат этих операций имеет тип boolean):

s1 = s2
s1 > s2
s1 < s2


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

{s: set of type1; k: type1}
for k:= min_type1 to max_type1
 do if k in s then write(k);

Представление множеств массивами
Одно из основных неудобств при работе с множествами - это 
ограничение размера всего лишь 256-ю элементами. Мы приведем здесь два очень 
похожих способа представления больших множеств массивами. Единственным условием 
является наличие некоторого внутреннего порядка среди представляемых элементов: 
без этого невозможно будет их перенумеровать.

Представление множеств линейными массивами
Задав линейный массив достаточной длины, можно "вручную" 
сымитировать множество для более широкого, чем 256 
элементов, диапазона значений. Например, чтобы работать с множеством, содержащим 10 000 элементов, достаточно такого 
массива:

set_arr: array[1..10000] of boolean;

При таком способе представления возможно задать множество до 65 000 элементов.

Для простоты изложения мы ограничимся только числовыми множествами, 
однако все сказанное ниже можно применять и к множествам, элементы которых имеют 
другую природу. Итак, признаком того, что элемент k 
является элементом нашего множества, будет значение true в k-й ячейке этого 
массива. 

Посмотрим теперь, какими способами мы вынуждены будем имитировать 
операции над "массивными" множествами. 



Проверка множества на пустоту может быть осуществлена 
довольно просто:

pusto:= true;
for i:= 1 to N do
 if set_arr[i] then begin pusto:= false;
 break
 end;


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

is_in:= set_arr[element];


Добавление элемента в множество 
нужно записывать так:

set_arr[element]:= true;


Удаление элемента из множества записывается аналогичным 
образом:

set_arr[element]:= false;

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

Проверка двух множеств на равенство не требует особых 
пояснений:

equal:= true;
for i:=1 1 to N do
 if set1[i]<> set2[i] 
 then begin equal:= false;
 break
 end;


Проверка двух множеств на включение (set1<set2) тоже не потребует больших усилий: 

subset:= true;
for i:= 1 to N do
 if set1[i]and not set2[i]
 then begin subset:= false;
 break
 end;
Представление множеств битовыми массивами
В случае, если 65 000 элементов недостаточно для задания всех 
необходимых множеств (например, 10 множеств по 10 000 элементов в каждом), это 
число можно увеличить в 8 раз, перейдя от байтов к битам. Тогда 1 байт будет 
хранить информацию не об одном, а сразу о восьми элементах: единичный бит будет 
означать наличие элемента в множестве, а нулевой бит - отсутствие.

Задавая битовый массив, начнем нумерацию 
его компонент с 0:

set_bit: array[0..N-1] of byte;

Тогда результатом операции <номер_элемента> div 8 будет номер той компоненты 
массива, в которой содержится информация об этом элементе. А вот номер бита, в 
котором содержится информация об этом элементе, придется вычислять более сложным 
образом:

bit:= <номер_элемента> mod 8;
if bit=0 then bit:= 8;

Эти вычисления потребуются нам еще не раз, поэтому запишем их 
снова, более строго, а затем будем использовать по умолчанию (element - это "номер" обрабатываемого элемента в нашем 
множестве):

kmp:= element div 8; {номер компоненты массива}
bit:= element mod 8; {номер бита}
if bit=0 then bit:= 8;

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



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

pusto:= true;
for i:= 0 to N-1 do
 if set_arr[i]<>0 then begin pusto:= false;
 break
 end;


Проверка элемента на принадлежность множеству потребует 
несколько большей изворотливости ведь нам теперь нужно вычленить соответствующий 
бит:

if set_arr[kmp]and(1 shl(bit-1))=0
 then is_in:= false
 else is_in:= true;

Поясним, что здесь используется операция "побитовое и" (см. лекцию 
2), которая работает непосредственно с битами нужной нам компоненты массива и 
числа, состоящего из семи нулей и единицы на месте с номером bit.


Добавление элемента в множество 
теперь будет записано так:

set_arr[kmp]:= set_arr[kmp]or(1 shl(bit-1));

Здесь нельзя использовать обычную операцию сложения (+), так как если добавляемый компонент уже содержится в 
множестве (то есть соответствующий бит уже имеет значение 1), то в результате сложения 1+1 получится 10: единица 
автоматически перенесется в старший бит, а на нужном месте окажется 0.


Удаление элемента из множества придется записать более 
сложным образом:

set_arr[kmp]:= set_arr[kmp]and not(1 shl(bit-1));

Операция not превратит все 0 в 1 и наоборот, 
следовательно, теперь в качестве второго операнда для побитового and будет фигурировать число, состоящее из семи единиц и 
нуля на месте с номером bit. Единицы сохранят любые 
значения тех битов, которые должны остаться без изменения, и лишь 0 "уничтожит" значение единственного нужного бита.


Пересечение множеств реализуется теперь при помощи операции 
"побитовое и":

for i:= 0 to N-1 do set_res[i]:= set1[i] and set2[i];


Объединение множеств реализуется при помощи операции 
"побитовое или":

for i:= 0 to N-1 do
 set_res[i]:= set1[i] or set2[i];


Разность двух множеств может быть построена так:

for i:= 0 to N-1 do
 set_res[i]:= (set1[i] or set2[i]) and not set2[i];

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


Проверка двух множеств на равенство по-прежнему не требует 
особых пояснений:

equal:= true;
for i:=0 to N-1 do
 if set1[i]<> set2[i] then begin equal:= false;
 break
 end;


Проверка двух множеств на включение (set1<set2) будет производиться по схеме: "Если (A\B)B=A, то 
BA ", 
доказательство которой настолько очевидно, что мы не станем на нем 
задерживаться:

subset:= true;
for i:= 0 to N-1 do
 if((set1[i] or set2[i])and not set2[i])
 or set2[i] <> set1[i]
 then begin subset:= false;
 break
 end;


Замечание. Если предстоит многократно выполнять действия с 
элементами битовых массивов, то используемые для 
этого значения "единиц" удобнее всего сразу задать в специальном массиве:

{ed: array[1..8] of byte;}
ed[1]:=1; 
for k:= 2 to 8 do 
 ed[k]:= ed[k-1] shl 1;

И далее вместо громоздкой конструкции 1 
shl(bit-1) можно использовать просто ed[bit].

Примеры использования символов, строк и множеств
Задача 1. Оставить в строке 
только первое вхождение каждого символа, взаимный 
порядок оставленных символов сохранить.

program z1;
var s: set of char;
inp, res: string;
i: byte;

begin
 s:=[];
 res:= '';
 for i:= 1 to length(inp) do
 if not(inp[i] in s)
 then begin res:= res+inp[i];
 s:= s+[inp[i]];
 end;
end.

Задача 2.1) Оставить в строке только последнее вхождение каждого символа, взаимный порядок оставленных символов сохранить.

program z2;
var inp, res: string; 
i: byte;

begin
 res:= '';
 for i:= 1 to length(inp) do
 begin 
 k:= pos(inp[i],res);
 if k<>0 
 then delete(res,k,1);
 res:= res+inp[i];
 end;
end.

Задача 3. Выдать первые 100 000 натуральных чисел в 
случайном порядке без повторений.

program z3;
var bset: array[0..12499] of byte; {множество, битовый 
массив}
 ed: array[1..8] of byte;
 el,k: longint;
 kmp,bin: integer;
begin
 ed[1]:= 1; {генерация массива 
битовых единиц}
 for k:= 2 to 8 do ed[k]:= ed[k-1] shl 1;
{-------------------------------------------------------}
 k:=0;
 randomize; {процедура активизации генератора случайных 
чисел}
 while k<100000 do
begin
 el:= 1+random(99999); {случайное число из диапазона 0..99999}
 kmp:= el div 8;
 bit:= el mod 8;
 if bit=0 then bit:= 8;
 if bset[kmp]and ed[bit]=0 {проверка повторов}
 then begin inc(k);
 writeln(el);
 bset[kmp]:= bset[kmp]or ed[bit]
 end;
end
end.