Изменения

{{Определение|definition=Генерация [[Комбинаторные объекты|комбинаторных объектов]] сгенерированы в [[Лексикографический порядок|лексикографическом порядке]] {{---}} непосредственное построение и перебор всех объектов заданного типа так, чтобы если для любых двух объектов выполнялось условие: <tex>K_ii<j </tex> выполняется неравенство <tex>S_i<S_j </tex> , где <tex>K_iS_i </tex>и <tex>_+S_j </tex>комбинаторные объекты с номерами <tex> i </tex> и <tex>_1j </tex>.}} 

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

'''for''' i = 1 .. '''to''' n '''if''' к объекту К можно добавить элемент aalpha[i] в конец genObj(K.pushback(a++ alpha[i]) genObj(K, p depth + 1, ans) <font color=green> //добавляем aalpha[i] в конец и вызываем функцию genObj от нового полученного префикса К.pop_back() </font>

*<tex>\mathtt{genChooses(k, l) }</tex> {{---}} процедура генерирования,*'''<tex>\mathtt{list \left<int\right>}</tex> <tex>''' \mathtt{a }</tex> {{---}} текущее сочетание,*'''int''' <tex>\mathtt{k }</tex> {{---}} следующий элемент в сочетании,*'''int''' <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) a[l] = k;:

ans.push_back(a) '''returnelse''' a '''for''' i = k + 1 '''to ''' n gen genChooses(i, l + 1, a ++ i, ans);

Иллюстрация работы процедуры генерирования всех сочетаний из генерации <tex dpi=150>\binom {4 по } {2.} </tex>

[[Файл:Chooses1211.jpgpng]]

== Ссылки См. также==* [[Получение номера по объекту]]* [[Получение объекта по номеру]] == Источники информации ==* [http://ru.wikipedia.org/wiki/Перечисление_(комбинаторика) Википедия — Перечисление (комбинаторика)]* [http://rain.ifmo.ru/cat/view.php/ ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫДискретная математика — Алгоритмы]* [http://algolist.ru/maths/combinat/ AlgoList — Комбинаторика и переборные задачи]* [http://e-maxx.ru/algo/ MAXimal :: Комбинаторика]