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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
  
−
Генерация [[Комбинаторные объекты|комбинаторных обьектов]] в [[Лексикографический порядок|лексикографическом порядке]] это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух обьектов выполнялось условие '''<math>K_i</math> <math><</math> <math>K_i</math>'''<math>_+</math><math>_1</math>.
+
Генерация [[Комбинаторные объекты|комбинаторных обьектов]] в [[Лексикографический порядок|лексикографическом порядке]] это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух обьектов выполнялось условие <tex>K_i</tex> <tex><</tex> <tex>K_i</tex><tex>_+</tex><tex>_1</tex>.
  
 
== Алгоритм построения ==
 
== Алгоритм построения ==
  
−
Составляем первый обьект - '''<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>'''.
+
==== Описание процедуры построения ====
 +
 
 +
Пусть <tex>Gen(p, X)</tex> процедура генерирования, где <tex>p</tex> - глубина рекурсии, <tex>K</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://rain.ifmo.ru/cat/view.php/ ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ]

Версия 07:43, 21 ноября 2010

Определение

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

Пример

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Генерация_комбинаторных_объектов_в_лексикографическом_порядке&oldid=5091»