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

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

2014-12-29T06:26:11Z

91.122.173.29: /* Источники информации */

Комбинаторные объекты сгенерированы в '''лексикографическом порядке''' ''(in lexicographical order)'', если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> комбинаторные объекты с номерами <tex> i </tex> и <tex> j </tex>.
== Алгоритм построения ==

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

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

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

'''list<A>''' genObj('''int''' K, '''int''' p):
'''if''' p == len // если сформирован объект нужного размера, то возвращаем его 
ans.push_back(K) // записываем объект K в ответ 
'''else'''
'''for''' i = 1 to 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>.

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

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

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

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

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

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

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

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

2014-12-29T06:11:13Z

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

Комбинаторные объекты сгенерированы в '''лексикографическом порядке''' ''(in lexicographical order)'', если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> комбинаторные объекты с номерами <tex> i </tex> и <tex> j </tex>.
== Алгоритм построения ==

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

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

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

'''list<A>''' genObj('''int''' K, '''int''' p):
'''if''' p == len // если сформирован объект нужного размера, то возвращаем его 
ans.push_back(K) // записываем объект K в ответ 
'''else'''
'''for''' i = 1 to 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>.

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

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

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

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

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

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

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

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

2014-12-29T06:01:37Z

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

Комбинаторные объекты сгенерированы в '''лексикографическом порядке''' ''(in lexicographical order)'', если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> комбинаторные объекты с номерами <tex> i </tex> и <tex> j </tex>.
== Алгоритм построения ==

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

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

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

'''list<A>''' genObj(int K,int p)
'''if''' p == len // если сформирован объект нужного размера, то возвращаем его 
ans.push_back(K) // записываем объект K в ответ 
'''else'''
'''for''' i = 1 to 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>.

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

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

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

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

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

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

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