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

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

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

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

 

 

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

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