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

Определение

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

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

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

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

Gen(p, K)
  if p = <требуемый размер обьекта>
    <выводим> K
  else
     for <все w из алфавита на котором строится K>
       if (K + w) = <корректный префикс требуемого обьекта>
         Gen(p + 1, K + w)

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

Составляем первый обьект - [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].

Ссылки

• Перечисление (комбинаторика)
• ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ