Изменения

[[Комбинаторные объекты ]] сгенерированы в '''[[Лексикографический порядок|лексикографическом порядке''' ''(in lexicographical order)'']] , если для любых <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, p␣␣depth)}</tex> {{---}} процедура генерирования,*<tex>\mathtt{ pdepth}</tex> {{---}} глубина рекурсии,*''<tex>\mathtt{list \left<A\right>}</tex>'' <tex>\mathtt{K}</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(int '''list<A>''' K,'''int p''' depth, '''list<list<A>>''' ans): '''if''' p depth == len <font color=green> // если сформирован объект нужного размера, то возвращаем его </font> ans.push_back(K); <font color=green>// записываем объект K в ответ </font>

'''for''' i = 1 '''to ''' n

genObj(K.push_back(++ alpha[i]) genObj(K, p depth + 1, ans) <font color=green> // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса </font> К.pop_back()

*''<tex>\mathtt{list \left<int\right>}</tex>'' <tex>\mathtt{a}</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) a[l] = k:

'''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://rain.ifmo.ru/cat/view.php/ Дискретная математика: алгоритмы— Алгоритмы]