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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Ссылки)
(→‎Описание процедуры построения)
Строка 5: Строка 5:
 
Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта.
 
Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта.
  
−
*<math>\mathrm{genObj(K, p)}</math> {{---}} процедура генерирования
+
*<tex>\mathrm{genObj(K, p)}</tex> {{---}} процедура генерирования
−
*''<math>\mathrm{int}</math>''  <math>\mathrm{ p}</math> {{---}} глубина рекурсии
+
*''<tex>\mathrm{int}</tex>''  <tex>\mathrm{ p}</tex> {{---}} глубина рекурсии
−
*''<math>\mathrm{list <A>}</math>'' <math>\mathrm{K}</math> {{---}} текущий комбинаторный объект.
+
*''<tex>\mathrm{list <A>}</tex>'' <tex>\mathrm{K}</tex> {{---}} текущий комбинаторный объект.
−
*''<math>\mathrm{int}</math>'' <math>\mathrm{len}</math> {{---}} требуемый размер объекта
+
*''<tex>\mathrm{int}</tex>'' <tex>\mathrm{len}</tex> {{---}} требуемый размер объекта
−
*''<math>\mathrm{list <A>}</math>'' <math>\mathrm{alpha}</math> {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
+
*''<tex>\mathrm{list <A>}</tex>'' <tex>\mathrm{alpha}</tex> {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
−
*''<math>\mathrm{int}</math>'' <math>\mathrm{n}</math> {{---}} размер alpha
+
*''<tex>\mathrm{int}</tex>'' <tex>\mathrm{n}</tex> {{---}} размер alpha
−
*''<math>\mathrm{list <list <A> >}</math>'' <math>\mathrm{ans}</math> {{---}} список, содержащий все сгенерированные объекты в нужном порядке
+
*''<tex>\mathrm{list <list <A> >}</tex>'' <tex>\mathrm{ans}</tex> {{---}} список, содержащий все сгенерированные объекты в нужном порядке
  
  

Версия 15:05, 30 ноября 2014

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

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

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

  • [math]\mathrm{genObj(K, p)}[/math] — процедура генерирования
  • [math]\mathrm{int}[/math] [math]\mathrm{ p}[/math] — глубина рекурсии
  • [math]\mathrm{list \lt A\gt }[/math] [math]\mathrm{K}[/math] — текущий комбинаторный объект.
  • [math]\mathrm{int}[/math] [math]\mathrm{len}[/math] — требуемый размер объекта
  • [math]\mathrm{list \lt A\gt }[/math] [math]\mathrm{alpha}[/math] — все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
  • [math]\mathrm{int}[/math] [math]\mathrm{n}[/math] — размер alpha
  • [math]\mathrm{list \lt list \lt A\gt \gt }[/math] [math]\mathrm{ans}[/math] — список, содержащий все сгенерированные объекты в нужном порядке


list <A> genObj(K, 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()

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

Составляем первый объект — [math]K_1[/math], для него получаем следующий объект — [math]K_2[/math], для [math]K_2[/math] получаем [math]K_3[/math], далее действуем также, для [math]K_i[/math] получая [math]K_i[/math][math]_+[/math][math]_1[/math] объект, пока не получим последний объект [math]K_n[/math].

Примеры

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

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

  • [math]\mathrm{genChooses(k, l)}[/math] — процедура генерирования
  • [math]\mathrm{list \lt int\gt }[/math] [math]\mathrm{a}[/math] — текущее сочетание
  • [math]\mathrm{int}[/math] [math]\mathrm{k}[/math] — следующий элемент в сочетании
  • [math]\mathrm{int}[/math] [math]\mathrm{l}[/math] — глубина рекурсии
  • [math]\mathrm{list \lt list \lt int\gt \gt ans}[/math] — все сгенерированные сочетания в нужном порядке
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://neerc.ifmo.ru/wiki/index.php?title=Генерация_комбинаторных_объектов_в_лексикографическом_порядке&oldid=41600»