Общие подходы к порождению комбинаторных объектов

При разработке алгоритмов часто возникает задача порождения комбинаторных объектов.

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

Алгоритм систематического порождения обычно строится по следующей схеме (1-я схема):

Замечание 1. При такой схеме необходимо учитывать, что алгоритм предпринимает еще одно преобразование после того, как выведен последний объект.

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

Случайное порождение комбинаторных объектов часто затруднено тем, что требуется равновероятность всех возможных конфигураций. В этом случае можно задать определенное взаимно однозначное соответствием между целыми числами 0,1,…, N -1 и N объектами, тогда случайное порождение осуществляется случайным порождением целого числа от 0 до N -1 и обращением его в объект. Такой же подход пригоден и для систематического порождения комбинаторных объектов. Систематическое порождение сводится к перечислению целых чисел от 0 до N -1 и обращением каждого числа в объект (2-я схема).

Замечание 2. Процесс обращения может быть долгим, тогда его следует избегать, если это возможно.