Генерация комбинаторных объектов в лексикографическом порядке — различия между версиями
(→Описание процедуры построения) |
(→Пример генерации сочетаний из N элементов по M в лексикографическом порядке) |
||
| Строка 38: | Строка 38: | ||
Данный алгоритм генерирует все сочетания из <tex>n</tex> элементов по <tex>m</tex>. | Данный алгоритм генерирует все сочетания из <tex>n</tex> элементов по <tex>m</tex>. | ||
| − | *genChooses(k, l) {{---}} процедура генерирования | + | *<math>\mathrm{genChooses(k, l)}</math> {{---}} процедура генерирования |
| − | *''list <int>'' a {{---}} текущее сочетание | + | *''<math>\mathrm{list <int>}</math>'' <math>\mathrm{a}</math> {{---}} текущее сочетание |
| − | *''int'' k {{---}} следующий элемент в сочетании | + | *''<math>\mathrm{int}</math>'' <math>\mathrm{k}</math> {{---}} следующий элемент в сочетании |
| − | *''int'' l {{---}} глубина рекурсии | + | *''<math>\mathrm{int}</math>'' <math>\mathrm{l}</math> {{---}} глубина рекурсии |
| − | *''list <list <int> > ans'' {{---}} все сгенерированные сочетания в нужном порядке | + | *''<math>\mathrm{list <list <int> > ans}</math>'' {{---}} все сгенерированные сочетания в нужном порядке |
'''list <int>''' genChooses(k, l) | '''list <int>''' genChooses(k, l) | ||
Версия 18:37, 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 в лексикографическом порядке
Данный алгоритм генерирует все сочетания из элементов по .
- — процедура генерирования
- — текущее сочетание
- — следующий элемент в сочетании
- — глубина рекурсии
- — все сгенерированные сочетания в нужном порядке
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.
