Генерация комбинаторных объектов в лексикографическом порядке

Материал из Викиконспекты
Перейти к: навигация, поиск

Определение

Генерация комбинаторных обьектов в лексикографическом порядке это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух обьектов выполнялось условие [math]K_i[/math] [math]\lt [/math] [math]K_i[/math][math]_+[/math][math]_1[/math].

Алгоритм построения

Описание процедуры построения

Пусть [math]Gen(p, X)[/math] процедура генерирования, где [math]p[/math] - глубина рекурсии, [math]K[/math] - комбинаторный обьект.


Генерация с помощью процедуры получения следующего обьекта

Составляем первый обьект - [math]K_1[/math], для него получаем следующий обьект - [math]K_2[/math], для [math]K_2[/math] получаем [math]K_3[/math], далее действуем также, для [math]K_i[/math] получая [math]K_i[/math][math]_+[/math][math]_1[/math] обьект, пока не получим последний обьект [math]K_n[/math].

Пример

Ссылки