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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Алгоритм построения)
Строка 7: Строка 7:
 
==== Описание процедуры построения ====
 
==== Описание процедуры построения ====
  
Пусть <tex>Gen(p, K)</tex> - процедура генерирования, где <tex>p</tex> - глубина рекурсии, <tex>K</tex> - комбинаторный обьект.
+
Пусть <tex>Gen(p, K)</tex> - процедура генерирования, где <tex>p</tex> - глубина рекурсии, <tex>K</tex> - комбинаторный объект.
  
 
  Gen(p, K)
 
  Gen(p, K)
   if p = <требуемый размер обьекта>
+
   if p = <требуемый размер объекта>
 
     <выводим> K
 
     <выводим> K
 
   else
 
   else
 
       for <все w из алфавита на котором строится K>
 
       for <все w из алфавита на котором строится K>
         if (K + w) = <корректный префикс требуемого обьекта>
+
         if (K + w) = <корректный префикс требуемого объекта>
 
           Gen(p + 1, K + w)
 
           Gen(p + 1, K + w)
  
==== Генерация с помощью процедуры получения следующего обьекта ====
+
==== Генерация с помощью процедуры получения следующего объекта ====
  
Составляем первый обьект - <tex>K_1</tex>, для него [[Получение следующего объекта|получаем следующий обьект]] - <tex>K_2</tex>, для <tex>K_2</tex> получаем <tex>K_3</tex>, далее действуем также, для <tex>K_i</tex> получая <tex>K_i</tex><tex>_+</tex><tex>_1</tex> обьект, пока не получим последний обьект <tex>K_n</tex>.
+
Составляем первый объект - <tex>K_1</tex>, для него [[Получение следующего объекта|получаем следующий объект]] - <tex>K_2</tex>, для <tex>K_2</tex> получаем <tex>K_3</tex>, далее действуем также, для <tex>K_i</tex> получая <tex>K_i</tex><tex>_+</tex><tex>_1</tex> объект, пока не получим последний объект <tex>K_n</tex>.
  
 
== Ссылки ==
 
== Ссылки ==
 
* [http://ru.wikipedia.org/wiki/Перечисление_(комбинаторика) Перечисление (комбинаторика)]
 
* [http://ru.wikipedia.org/wiki/Перечисление_(комбинаторика) Перечисление (комбинаторика)]
 
* [http://rain.ifmo.ru/cat/view.php/ ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ]
 
* [http://rain.ifmo.ru/cat/view.php/ ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ]

Версия 19:31, 21 ноября 2010

Определение

Генерация комбинаторных объектов в лексикографическом порядке - это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух объектов выполнялось условие: [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].

Ссылки