Изменения

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

Пусть *<tex>Gen\mathtt{genObj(K, p␣␣depth)}</tex> {{---}} процедура генерирования, где *<tex>p\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> {{---}} список, содержащий все сгенерированные объекты в нужном порядке.

Gen '''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> '''else''' '''for <все w из алфавита на котором строится K>''' i = 1 '''to''' n '''if (K + w) = <корректный префикс требуемого объекта>''' к объекту К можно добавить элемент alpha[i] в конец GengenObj(K + w+ alpha[i], p depth + 1, ans) <font color=green> // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса </font>

Пусть Данный алгоритм генерирует все сочетания из <tex>gen(k, l)n</tex> {{---}} процедура генерирования, где элементов по <tex>am</tex> {{---}} текущее сочетание, <tex>k</tex> {{---}} следующий элемент в сочетании, <tex>l</tex> {{---}} глубина рекурсии.

gen*<tex>\mathtt{genChooses(k, l);}</tex> {{---}} процедура генерирования, *<tex>\mathtt{list\left<int\right>}</tex> <tex>\mathtt{a[l] = }</tex> {{---}} текущее сочетание,*<tex>\mathtt{k;}</tex> {{---}} следующий элемент в сочетании, if *<tex>\mathtt{l = m then }</tex> {{---}} глубина рекурсии,*<tex>\mathtt{list\left<list\left<int\right>\right>\ ans}<проверка на требуемый размер объекта/tex>{{---}} все сгенерированные сочетания в нужном порядке. begin for j = 1 to m do write '''list<int>''' genChooses('''int''' k, '''int''' l, '''list<int>''' a[j], ' '); 'list<list<вывод объектаint>>''' ans): writeln; '''if''' l == m end ans.push_back(a) '''else ''' '''for ''' i = k + 1 '''to ''' n do gen genChooses(i, l + 1, a ++ i, ans);

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

[[Файл:imagesperes1211.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 :: Комбинаторика]