1632
правки
Изменения
м
'''list <A>''' genObj('''list<A>''' K, p'''int''' depth, '''list<list<A>>''' ans): '''if''' p depth == len <font color=green> // если сформирован объект нужного размера, то возвращаем его </font> ans.push_back(K); <font color=green>// записываем объект K в ответ</font>
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>\mathrmmathtt{genObj(K, p␣␣depth)}</tex> {{---}} процедура генерирования,*''<tex>\mathrmmathtt{int}</tex>'' <tex>\mathrm{ pdepth}</tex> {{---}} глубина рекурсии,*''<tex>\mathrmmathtt{list \left<A\right>}</tex>'' <tex>\mathrmmathtt{K}</tex> {{---}} текущий комбинаторный объект.,*''<tex>\mathrm{int}</tex>'' <tex>\mathrmmathtt{len}</tex> {{---}} требуемый размер объекта,*''<tex>\mathrmmathtt{list \left<A\right>}</tex>'' <tex>\mathrmmathtt{alpha}</tex> {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке,*''<tex>\mathrmmathtt{intn}</tex>'' {{---}} размер <tex>\mathrmmathtt{nalpha}</tex> {{---}} размер alpha,*''<tex>\mathrmmathtt{list \left<list \left<A\right> \right>}</tex>'' <tex>\mathrmmathtt{ans}</tex> {{---}} список, содержащий все сгенерированные объекты в нужном порядке.
'''else'''
'''for''' i = 1 '''to ''' n
'''if''' к объекту К можно добавить элемент alpha[i] в конец
genObj(K.push_back(++ alpha[i]) genObj(K, p depth + 1, ans) <font color=green> // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса К.pop_back()</font>
==== Генерация с помощью процедуры получения следующего объекта ====
Данный алгоритм генерирует все сочетания из <tex>n</tex> элементов по <tex>m</tex>.
*<tex>\mathrmmathtt{genChooses(k, l)}</tex> {{---}} процедура генерирования,*''<tex>\mathrmmathtt{list \left<int\right>}</tex>'' <tex>\mathrmmathtt{a}</tex> {{---}} текущее сочетание,*''<tex>\mathrm{int}</tex>'' <tex>\mathrmmathtt{k}</tex> {{---}} следующий элемент в сочетании,*''<tex>\mathrm{int}</tex>'' <tex>\mathrmmathtt{l}</tex> {{---}} глубина рекурсии,*''<tex>\mathrmmathtt{list \left<list \left<int\right> \right> \ ans}</tex>'' {{---}} все сгенерированные сочетания в нужном порядке.
'''list <int>''' genChooses('''int''' k, '''int''' l, '''list<int>''' a, '''list<list<int>>''' ans) a[l] = k;:
'''if''' l == m
ans.push_back(a)
'''else''' '''for''' i = k + 1 '''to ''' n genChooses(i, l + 1, a ++ i, ans);
==== Пример работы процедуры генерации ====
Иллюстрация работы процедуры генерирования всех сочетаний из генерации <tex dpi=150>\binom {4 по } {2} </tex> [[Файл:1211.png]]
==См. также==* [[Получение номера по объекту]]* [[Файл:4 2 s.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 :: Комбинаторика]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
[[Категория: Генерация комбинаторных объектов]]
