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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Описание процедуры построения)
Строка 10: Строка 10:
  
 
*genObj(K, p) {{---}} процедура генерирования
 
*genObj(K, p) {{---}} процедура генерирования
−
*'''int''' p {{---}} глубина рекурсии
+
*''int'' p {{---}} глубина рекурсии
−
*'''list <A>''' K {{---}} текущий комбинаторный объект.
+
*''list <A>'' K {{---}} текущий комбинаторный объект.
−
*'''int''' len {{---}} требуемый размер объекта
+
*''int'' len {{---}} требуемый размер объекта
−
*'''list <A>''' alpha {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
+
*''list <A>'' alpha {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
−
*'''int''' n {{---}} размер alpha
+
*''int'' n {{---}} размер alpha
 +
*''list <A>'' ans {{---}} список, содержащий все сгенерированные объекты в нужном порядке
  
  
 
  '''list <A>''' genObj(K, p)
 
  '''list <A>''' genObj(K, p)
 
   '''if''' p == len                            // если сформирован объект нужного размера, то возвращаем его     
 
   '''if''' p == len                            // если сформирован объект нужного размера, то возвращаем его     
−
     '''yield''' K                               // возвращаем объект K с сохранением состояния перебора
+
     ans.push_back(K);                    // записываем объект K в ответ
 
   '''else'''
 
   '''else'''
 
     '''for''' i = 1 .. n                         
 
     '''for''' i = 1 .. n                         
−
         '''if''' к объекту К можно добавить элемент a[i] в конец
+
         '''if''' к объекту К можно добавить элемент alpha[i] в конец
−
           K.push_back(a[i])                       
+
           K.push_back(alpha[i])                       
−
           genObj(K, p + 1)                     // добавляем a[i] в конец и вызываем функцию genObj от нового полученного префикса
+
           genObj(K, p + 1)                 // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса
 
           К.pop_back()
 
           К.pop_back()
  
Строка 38: Строка 39:
  
 
*genChooses(k, l) {{---}} процедура генерирования
 
*genChooses(k, l) {{---}} процедура генерирования
−
*'''list <int>''' a {{---}} текущее сочетание
+
*''list <int>'' a {{---}} текущее сочетание
−
*'''int''' k {{---}} следующий элемент в сочетании
+
*''int'' k {{---}} следующий элемент в сочетании
−
*'''int''' l {{---}} глубина рекурсии
+
*''int'' l {{---}} глубина рекурсии
 +
*''list <list <int> > ans'' {{---}} все сгенерированные сочетания в нужном порядке
  
 
  '''list <int>''' genChooses(k, l)
 
  '''list <int>''' genChooses(k, l)
 
   a[l] = k;
 
   a[l] = k;
 
   '''if''' l == m         
 
   '''if''' l == m         
−
     '''return''' a
+
     ans.push_back(a)
 
   '''for''' i = k + 1 to n
 
   '''for''' i = k + 1 to n
 
     genChooses(i, l + 1);
 
     genChooses(i, l + 1);

Версия 11:23, 4 января 2014

Определение:
Генерация комбинаторных объектов в лексикографическом порядке — непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух объектов выполнялось условие: [math]K_i[/math] [math]\lt [/math] [math]K_i[/math][math]_+[/math][math]_1[/math].


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

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

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

  • genObj(K, p) — процедура генерирования
  • int p — глубина рекурсии
  • list <A> K — текущий комбинаторный объект.
  • int len — требуемый размер объекта
  • list <A> alpha — все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
  • int n — размер alpha
  • 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()

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

Составляем первый объект — [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].

  • 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://neerc.ifmo.ru/wiki/index.php?title=Генерация_комбинаторных_объектов_в_лексикографическом_порядке&oldid=35016»