Генерация комбинаторных объектов в лексикографическом порядке — различия между версиями
| Строка 1: | Строка 1: | ||
== Определение == | == Определение == | ||
| − | Генерация [[Комбинаторные объекты|комбинаторных обьектов]] в [[Лексикографический порядок|лексикографическом порядке]] это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух обьектов выполнялось условие <tex>K_i</tex> <tex><</tex> <tex>K_i</tex><tex>_+</tex><tex>_1</tex>. | + | Генерация [[Комбинаторные объекты|комбинаторных обьектов]] в [[Лексикографический порядок|лексикографическом порядке]] - это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух обьектов выполнялось условие: <tex>K_i</tex> <tex><</tex> <tex>K_i</tex><tex>_+</tex><tex>_1</tex>. |
== Алгоритм построения == | == Алгоритм построения == | ||
| Строка 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) | ||
| Строка 13: | Строка 13: | ||
<выводим> K | <выводим> K | ||
else | else | ||
| − | for <все w из алфавита на котором | + | for <все w из алфавита на котором строится K> |
if (K + w) = <корректный префикс требуемого обьекта> | if (K + w) = <корректный префикс требуемого обьекта> | ||
Gen(p + 1, K + w) | Gen(p + 1, K + w) | ||
| Строка 20: | Строка 20: | ||
Составляем первый обьект - <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/ ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ] | ||
Версия 09:26, 21 ноября 2010
Содержание
Определение
Генерация комбинаторных обьектов в лексикографическом порядке - это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух обьектов выполнялось условие: .
Алгоритм построения
Описание процедуры построения
Пусть - процедура генерирования, где - глубина рекурсии, - комбинаторный обьект.
Gen(p, K)
if p = <требуемый размер обьекта>
<выводим> K
else
for <все w из алфавита на котором строится K>
if (K + w) = <корректный префикс требуемого обьекта>
Gen(p + 1, K + w)
Генерация с помощью процедуры получения следующего обьекта
Составляем первый обьект - , для него получаем следующий обьект - , для получаем , далее действуем также, для получая обьект, пока не получим последний обьект .
