Изменения

Перейти к: навигация, поиск
м
rollbackEdits.php mass rollback
{{Определение|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>
'''else'''
'''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>n</tex> элементов по <tex>m</tex>.
*<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;:
'''if''' l == m
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 :: Комбинаторика]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
 
[[Категория: Генерация комбинаторных объектов]]
1632
правки

Навигация