Генерация комбинаторных объектов в лексикографическом порядке

2014-08-11T19:17:05Z

77.234.15.195: /* Описание процедуры построения */

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

== Алгоритм построения ==

==== Описание процедуры построения ====

Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта.

*genObj(K, p) {{---}} процедура генерирования
*''int'' p {{---}} глубина рекурсии
*''list <A>'' K {{---}} текущий комбинаторный объект.
*''int'' len {{---}} требуемый размер объекта
*''list <A>'' alpha {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
*''int'' n {{---}} размер alpha
*''list <list <A> >'' ans {{---}} список, содержащий все сгенерированные объекты в нужном порядке

'''list <A>''' genObj(K, p)
'''if''' p == len // если сформирован объект нужного размера, то возвращаем его
ans.push_back(K); // записываем объект K в ответ
'''else'''
'''for''' i = 1 .. n
'''if''' к объекту К можно добавить элемент alpha[i] в конец
K.push_back(alpha[i])
genObj(K, p + 1) // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса
К.pop_back()

==== Генерация с помощью процедуры получения следующего объекта ====

Составляем первый объект {{---}} <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 элементов по M в лексикографическом порядке ====

Данный алгоритм генерирует все сочетания из <tex>n</tex> элементов по <tex>m</tex>.

*genChooses(k, l) {{---}} процедура генерирования
*''list <int>'' a {{---}} текущее сочетание
*''int'' k {{---}} следующий элемент в сочетании
*''int'' l {{---}} глубина рекурсии
*''list <list <int> > ans'' {{---}} все сгенерированные сочетания в нужном порядке

'''list <int>''' genChooses(k, l)
a[l] = k;
'''if''' l == m
ans.push_back(a)
'''for''' i = k + 1 to n
genChooses(i, l + 1);

==== Пример работы процедуры генерации ====

Иллюстрация работы процедуры генерирования всех сочетаний из 4 по 2.

[[Файл:Chooses.jpg]]

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

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

Викиконспекты - Вклад участника [ru]

Генерация комбинаторных объектов в лексикографическом порядке