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

Основными вопросами, которые при этом изучаются, являются следующие:

• Как подсчитать количество элементов в множестве М?

• Как эффективно (под эффективностью в этой главе мы понимаем скорость работы программы, а не просто существование полиномиального алгоритма, как обычно) перечислить (сгенерировать) все элементы множества М, каждое ровно один раз?

• Пусть на множестве М определен некоторый порядок. Как эффективно перечислить элементы М именно в этом порядке?

• Как по объекту х М получить следующий или предыдущий в заданном порядке? Как определить порядок, чтобы соседние объекты отличались как можно меньше?

• Как по объекту х М найти его номер для заданного порядка, и наоборот, по номеру - элемент? Как определить порядок, чтобы эти операции выполнялись эффективно?

Хорошим введением в очерченный круг вопросов может служить глава 1 книги [Липский 88]. Также порекомендуем главу 2 книги [Шень95]. Для обучения искусству составления комбинаторных  алгоритмов  авторы устраивают так называемые блиц-туры по комбинаторике (пример такого блиц-тура приведен в 5.1). Они заключаются в максимально быстром решении как можно большего количества комбинаторных задач. Среди этих задач даются как стандартные задачи, вроде генерирования перестановок, так и нестандартные, вроде подсчета разбиений числа N на сумму от К до L слагаемых, каждое из которых принадлежит диапазону от А до В. Первые из них необходимы для выработки автоматизма при программировании наиболее часто встречающихся комбинаторных алгоритмов, вторые - для развития умения придумывать такого рода алгоритмы самостоятельно

Решение задач из этой главы требует знания динамического программирования и умения реализовать длинную арифметику (см. главу 1). Как правило, достаточно запрограммировать сложение и вычитание длинных чисел, а также умножение и деление длинного числа на короткое

Комбинаторные алгоритмы обычно нужны не сами по себе, а как часть решения более сложной задачи. Задачи "Отравленный пирог" и "За двумя мышками погонишься ...", игровые по своей сути, попали сюда в качестве иллюстрации применения таких алгоритмов для нумерации состояний, возникающих в игре. Для их решения полезно знать технику работы с графами, описанную в главе 3