1632
правки
Изменения
м
Генерация [[Комбинаторные Данный алгоритм генерирует все объекты|комбинаторных обьектов]] заданного типа в [[Лексикографический порядок|лексикографическом порядке]] это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух обьектов выполнялось условие <tex>K_i</tex> <tex><</tex> <tex>K_i</tex><tex>_+</tex><tex>_1</tex>. На каждом шаге генерируется минимальный возможный префикс требуемого объекта.
Пусть Иллюстрация работы процедуры генерации <texdpi=150>Gen(p, X)\binom {4} {2} </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/ ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ]
rollbackEdits.php mass rollback
[[Комбинаторные объекты]] сгенерированы в [[Лексикографический порядок|лексикографическом порядке]] , если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> комбинаторные объекты с номерами <tex> i </tex> и <tex> j </tex>.== Алгоритм построения == ==== Описание процедуры построения == Определение ==
*<tex>\mathtt{genObj(K, ␣␣depth)}</tex> {{---}} процедура генерирования,*<tex>\mathtt{depth}</tex> {{---}} глубина рекурсии,*<tex>\mathtt{list\left<A\right>}</tex> <tex>\mathtt{K}</tex> {{---}} текущий комбинаторный объект,* <tex>\mathtt{len}</tex> {{---}} требуемый размер объекта,*<tex>\mathtt{list\left<A\right>}</tex> <tex>\mathtt{alpha}</tex> {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке,* <tex>\mathtt{n}</tex> {{---}} размер <tex>\mathtt{alpha}</tex>,*<tex>\mathtt{list\left<list\left<A\right>\right>}</tex> <tex>\mathtt{ans}</tex> {{---}} список, содержащий все сгенерированные объекты в нужном порядке. '''list<A>''' genObj('''list<A>''' K, '''int''' depth, '''list<list<A>>''' ans): '''if''' depth == Алгоритм построения len <font color=green> // если сформирован объект нужного размера, то возвращаем его </font> ans.push_back(K) <font color=green>// записываем объект K в ответ </font> '''else''' '''for''' i = 1 '''to''' n '''if''' к объекту К можно добавить элемент alpha[i] в конец genObj(K ++ alpha[i], depth + 1, ans) <font color=green> // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса </font> ==== Генерация с помощью процедуры получения следующего объекта ==== Составляем первый объект {{---}} <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>. == Примеры == ==== Пример генерации сочетаний из N элементов по M в лексикографическом порядке ==== Данный алгоритм генерирует все сочетания из <tex>n</tex> элементов по <tex>m</tex>. *<tex>\mathtt{genChooses(k, l)}</tex> {{---}} процедура генерирования,*<tex>\mathtt{list\left<int\right>}</tex> <tex>\mathtt{a}</tex> {{---}} текущее сочетание,*<tex>\mathtt{k}</tex> {{---}} следующий элемент в сочетании,*<tex>\mathtt{l}</tex> {{---}} глубина рекурсии,*<tex>\mathtt{list\left<list\left<int\right>\right>\ ans}</tex> {{---}} все сгенерированные сочетания в нужном порядке. '''list<int>''' genChooses('''int''' k, '''int''' l, '''list<int>''' a, '''list<list<int>>''' ans): '''if''' l == m ans.push_back(a) '''else''' '''for''' i = k + 1 '''to''' n genChooses(i, l + 1, a ++ i, ans)
==== Описание Пример работы процедуры построения генерации ====
[[Файл:1211.png]]
==См. также==
* [[Получение номера по объекту]]
* [[Получение объекта по номеру]]
==Источники информации == Генерация с помощью процедуры получения следующего обьекта ====* [http://ru.wikipedia.org/wiki/Перечисление_(комбинаторика) Википедия — Перечисление (комбинаторика)]* [http://rain.ifmo.ru/cat/view.php/ Дискретная математика — Алгоритмы]* [http://algolist.ru/maths/combinat/ AlgoList — Комбинаторика и переборные задачи]* [http://e-maxx.ru/algo/ MAXimal :: Комбинаторика]
