Содержание

• Содержание
  • Представление множеств массивами
    • Представление множеств битовыми массивами
  • Примеры использования символов, строк и множеств
• Примечания

Представление множеств массивами

Представление множеств битовыми массивами

В случае, если 65 000 элементов недостаточно для задания всех необходимых множеств (например, 10 множеств по 10 000 элементов в каждом), это число можно увеличить в 8 раз, перейдя от байтов к битам. Тогда 1 байт будет хранить информацию не об одном, а сразу о восьми элементах: единичный бит будет означать наличие элемента в множестве, а нулевой бит — отсутствие.

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

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

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

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

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

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

   pusto := True;
   for i := 0 to N - 1 do
    if set_arr[i] <> 0 then
    begin
       pusto := False;
      Break
    end;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   equal := True;
   for i := 0 to N - 1 do
    if set1[i] <> set2[i] then
    begin
       equal := False;
      Break
    end;

9. Проверка двух множеств на включение (set1 < set2) будет производиться по схеме: «Если set1 - set2 = [], то set1 < set2», доказательство которой настолько очевидно, что мы не станем на нём задерживаться:

   subset := True;
   for i := 0 to N - 1 do
    if (set1[i] and not set2[i]) <> 0 then
    begin
       subset := False;
      Break
    end;

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

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

Примеры использования символов, строк и множеств

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

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

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

Примечания

1. ^ Более простой вариант решения — повторить решение задачи 1 с заменой цикла for-to на for-downto. Приведённый же вариант решения можно использовать для обработки не только строк, но и файлов.