Генерация комбинаторных объектов в лексикографическом порядке — различия между версиями
(→Описание процедуры построения) |
(→Описание процедуры построения) |
||
| Строка 9: | Строка 9: | ||
Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта. | Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта. | ||
| − | *genObj(K, p) {{---}} процедура генерирования | + | *<math>\mathrm{genObj(K, p)}</math> {{---}} процедура генерирования |
| − | *''int'' p {{---}} глубина рекурсии | + | *''<math>\mathrm{int}</math>'' <math>\mathrm{ p}</math> {{---}} глубина рекурсии |
| − | *''list <A>'' K {{---}} текущий комбинаторный объект. | + | *''<math>\mathrm{list <A>}</math>'' <math>\mathrm{K}</math> {{---}} текущий комбинаторный объект. |
| − | *''int'' len {{---}} требуемый размер объекта | + | *''<math>\mathrm{int}</math>'' <math>\mathrm{len}</math> {{---}} требуемый размер объекта |
| − | *''list <A>'' alpha {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке | + | *''<math>\mathrm{list <A>}</math>'' <math>\mathrm{alpha}</math> {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке |
| − | *''int'' n {{---}} размер alpha | + | *''<math>\mathrm{int}</math>'' <math>\mathrm{n}</math> {{---}} размер alpha |
| − | *''list <list <A> >'' ans {{---}} список, содержащий все сгенерированные объекты в нужном порядке | + | *''<math>\mathrm{list <list <A> >}</math>'' <math>\mathrm{ans}</math> {{---}} список, содержащий все сгенерированные объекты в нужном порядке |
Версия 18:28, 24 ноября 2014
| Определение: |
| Генерация комбинаторных объектов в лексикографическом порядке — непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух объектов выполнялось условие: . |
Содержание
Алгоритм построения
Описание процедуры построения
Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта.
- — процедура генерирования
- — глубина рекурсии
- — текущий комбинаторный объект.
- — требуемый размер объекта
- — все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
- — размер alpha
- — список, содержащий все сгенерированные объекты в нужном порядке
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()
Генерация с помощью процедуры получения следующего объекта
Составляем первый объект — , для него получаем следующий объект — , для получаем , далее действуем также, для получая объект, пока не получим последний объект .
Примеры
Пример генерации сочетаний из N элементов по M в лексикографическом порядке
Данный алгоритм генерирует все сочетания из элементов по .
- 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.
