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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта.
 
Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта.
  
−
Пусть <tex>Gen(K, p)</tex> {{---}} процедура генерирования, где <tex>p</tex> {{---}} глубина рекурсии, <tex>K</tex> {{---}} комбинаторный объект.
+
*genObj(K, p) {{---}} процедура генерирования
 +
*'''int''' p {{---}} глубина рекурсии
 +
*'''list <A>''' K {{---}} текущий комбинаторный объект.
 +
*'''int''' len {{---}} требуемый размер объекта
 +
*'''list <A>''' alpha {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке
 +
*'''int''' n {{---}} размер alpha
  
−
  Gen(K, p)
+
 
−
   if p = <требуемый размер объекта>
+
  '''list <A>''' genObj(K, p)
−
     <выводим> K
+
   '''if''' p == len                            //если сформирован объект нужного размера, то возвращаем его   
−
   else
+
     '''return''' K
−
      for <все w из алфавита на котором строится K>
+
   '''else'''
−
         if (K + w) = <корректный префикс требуемого объекта>
+
    '''for''' i = 1 .. n                       
−
           Gen(K + w, p + 1)
+
         '''if''' к объекту К можно добавить элемент a[i] в конец
 +
          K.pushback(a[i])                    
 +
           genObj(K, p + 1)                     //добавляем a[i] в конец и вызываем функцию genObj от нового полученного префикса
 +
          К.pop_back()       
  
 
==== Генерация с помощью процедуры получения следующего объекта ====
 
==== Генерация с помощью процедуры получения следующего объекта ====
Строка 27: Строка 35:
 
==== Пример генерации сочетаний из N элементов по M в лексикографическом порядке ====
 
==== Пример генерации сочетаний из N элементов по M в лексикографическом порядке ====
  
−
Пусть <tex>gen(k, l)</tex> {{---}} процедура генерирования, где <tex>a</tex> {{---}} текущее сочетание, <tex>k</tex> {{---}} следующий элемент в сочетании,      <tex>l</tex> {{---}} глубина рекурсии.
+
Данный алгоритм генерирует все сочетания из <tex>n</tex> элементов по <tex>m</tex>.
 +
 
 +
*genChooses(k, l) {{---}} процедура генерирования
 +
*'''list <int>''' a {{---}} текущее сочетание
 +
*'''int''' k {{---}} следующий элемент в сочетании
 +
*'''int''' l {{---}} глубина рекурсии
  
−
  gen(k, l);
+
  '''list <int>''' genChooses(k, l)
−
    a[l] = k;
+
  a[l] = k;
−
    if l = m then <проверка на требуемый размер объекта>
+
  '''if''' l == m      
−
     begin
+
     '''return''' a
−
        for j = 1 to m do write(a[j], ' '); <вывод объекта>
+
  '''for''' i = k + 1 to n
−
        writeln;
+
    gen(i, l + 1);
−
    end else for i = k + 1 to n do gen(i, l + 1);
 
  
 
==== Пример работы процедуры генерации ====
 
==== Пример работы процедуры генерации ====

Версия 18:38, 26 декабря 2013

Определение:
Генерация комбинаторных объектов в лексикографическом порядке — непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух объектов выполнялось условие: [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> genObj(K, p)
  if p == len                             //если сформирован объект нужного размера, то возвращаем его    
    return K
  else
    for i = 1 .. n                        
       if к объекту К можно добавить элемент a[i] в конец
         K.pushback(a[i])                      
         genObj(K, p + 1)                      //добавляем a[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 <int> genChooses(k, l)
  a[l] = k;
  if l == m        
    return a
  for i = k + 1 to n
    gen(i, l + 1);

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

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

Chooses.jpg

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Генерация_комбинаторных_объектов_в_лексикографическом_порядке&oldid=34754»