Генерация комбинаторных объектов в лексикографическом порядке — различия между версиями
(→Определение) |
(→Алгоритм построения) |
||
| Строка 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>. |
== Ссылки == | == Ссылки == | ||
* [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
Содержание
Определение
Генерация комбинаторных объектов в лексикографическом порядке - это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух объектов выполнялось условие: .
Алгоритм построения
Описание процедуры построения
Пусть - процедура генерирования, где - глубина рекурсии, - комбинаторный объект.
Gen(p, K)
if p = <требуемый размер объекта>
<выводим> K
else
for <все w из алфавита на котором строится K>
if (K + w) = <корректный префикс требуемого объекта>
Gen(p + 1, K + w)
Генерация с помощью процедуры получения следующего объекта
Составляем первый объект - , для него получаем следующий объект - , для получаем , далее действуем также, для получая объект, пока не получим последний объект .
