Алгоритмы теории множеств нередко применяются в программировании. В этой статье я хочу поговорить о генерации подмножеств множества. Множество — это набор элементов. Все элементы множества различны, то есть один элемент не может встретиться в множестве дважды. Программно реализовать множество можно разными способами: в виде класса, в виде массива с функциями для операций над ним и т.д. В языке Pascal имеется готовая реализация и синтаксис для работы со множествами.

Генерация подмножеств множества может пригодиться, допустим, в логике игры, когда из набора персонажей необходимо выбрать случайную их группу. Допустим, имеется множество M = {1, 2, 3}. Все подмножества множества M (их совокупность называют булеаном) следующие:

{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

И снова всем привет! После вводной статьи самое время рассмотреть какую-нибудь задачку. Для первого раза возьмем простенькую, чтобы, так сказать, войти в курс дела.

Итак, задача о ящике. Условие задачи взято из системы Cats сайта ДВГУ. Оно на английском языке, я кратко опишу суть. Имеется шесть досок определенного размера (ширина и высота). Необходимо определить, можно ли из этих досок собрать ящик. Входной файл box.in содержит шесть строк, каждая описывает размер доски и состоит из двух чисел w и h — ширины и высоты. Выходной файл box.out должен содержать слово POSSIBLE, если возможно из данных шести досок собрать ящик, либо IMPOSSIBLE, если это невозможно. Ограничение по времени выполнения: 2 секунды, по памяти: 64 Mb. 1 ≤ w, h ≤ 10000.