Изменения

== Определение == Генерация [[Комбинаторные объекты|комбинаторных объектов]] сгенерированы в [[Лексикографический порядок|лексикографическом порядке]] {{---}} непосредственное построение и перебор всех объектов заданного типа так, чтобы если для любых двух объектов выполнялось условие: <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(pK, K␣␣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(p'''list<A>''' K, '''int''' depth, K'''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 ''' к объекту К можно добавить элемент alpha[i] в конец genObj(K + w+ alpha[i], depth + 1, ans) <font color= green> // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса <корректный префикс требуемого объекта/font> Gen(p + 1, K + w)

Составляем первый объект {{- --}} <tex>K_1</tex>, для него [[Получение следующего объекта|получаем следующий объект]] {{--- }} <tex>K_2</tex>, для <tex>K_2</tex> получаем <tex>K_3</tex>, далее действуем также, для <tex>K_i</tex> получая <tex>K_i</tex><tex>_+</tex><tex>_1</tex> объект, пока не получим последний объект <tex>K_n</tex>.

==== Пример генерации сочетаний из N элементов по K M в лексикографическом порядке ====

Первым сочетанием, очевидно, будет сочетание Данный алгоритм генерирует все сочетания из <tex>(1,2,...,K)n</tex> элементов по <tex>m</tex>. Научимся для текущего сочетания находить лексикографически следующее. Для этого в текущем сочетании найдём самый правый элемент, не достигший ещё своего наибольшего значения; тогда увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения.

Пусть *<tex>next_combination \mathtt{genChooses(ak, nl)}</tex> {{--- }} процедура генерирования, где *<tex>\mathtt{list\left<int\right>}</tex> <tex>\mathtt{a}</tex> {{- --}} текущее сочетание, *<tex>\mathtt{k}</tex> {{---}} следующий элемент в сочетании,*<tex>n\mathtt{l}</tex> {{---}} глубина рекурсии,*<tex>\mathtt{list\left<list\left<int\right>\right>\ ans}</tex> {{--- количество элементов}} все сгенерированные сочетания в нужном порядке.

bool next_combination '''list<int>''' genChooses(vector'''int''' k, '''int''' l, '''list<int> & ''' a, '''list<list<int n>>''' ans) {: int k '''if''' l == m ans.push_back(int)a.size(); '''else''' '''for (int ''' i=k-+ 1; i>=0; --i)'''to''' n if genChooses(a[i] < n-k+i, l +1) { , a ++a[i]; for (int j=i+1; j<k; ++j, ans) a[j] = a[j-1]+1; return true; } return false; }

Иллюстрация работы процедуры генерирования всех перестановок из чисел генерации <texdpi=150>1, \binom {4} {2, 3} </tex> [[Файл:1211.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 :: Комбинаторика] [[Категория: Дискретная математика и алгоритмы]]

[[ФайлКатегория:Gen_Perm.pngКомбинаторика ]]

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