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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
м (rollbackEdits.php mass rollback)
 
(не показано 99 промежуточных версий 15 участников)
Строка 1: Строка 1:
== Определение ==
+
[[Комбинаторные объекты]] сгенерированы в [[Лексикографический порядок|лексикографическом порядке]] , если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> комбинаторные объекты с номерами <tex> i </tex> и <tex> j </tex>.
 
 
Генерация [[Комбинаторные объекты|комбинаторных объектов]] в [[Лексикографический порядок|лексикографическом порядке]] - это непосредственное построение и перебор всех объектов заданного типа так, чтобы для любых двух объектов выполнялось условие: <tex>K_i</tex> <tex><</tex> <tex>K_i</tex><tex>_+</tex><tex>_1</tex>.
 
 
 
 
== Алгоритм построения ==
 
== Алгоритм построения ==
  
 
==== Описание процедуры построения ====
 
==== Описание процедуры построения ====
  
Пусть <tex>Gen(p, K)</tex> - процедура генерирования, где <tex>p</tex> - глубина рекурсии, <tex>K</tex> - комбинаторный объект.
+
Данный алгоритм генерирует все объекты заданного типа в лексикографическом порядке. На каждом шаге генерируется минимальный возможный префикс требуемого объекта.
 +
 
 +
*<tex>\mathtt{genObj(K, ␣␣depth)}</tex> {{---}} процедура генерирования,
 +
*<tex>\mathtt{depth}</tex> {{---}} глубина рекурсии,
 +
*<tex>\mathtt{list\left<A\right>}</tex> <tex>\mathtt{K}</tex> {{---}} текущий комбинаторный объект,
 +
* <tex>\mathtt{len}</tex> {{---}} требуемый размер объекта,
 +
*<tex>\mathtt{list\left<A\right>}</tex> <tex>\mathtt{alpha}</tex> {{---}} все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке,
 +
* <tex>\mathtt{n}</tex> {{---}} размер <tex>\mathtt{alpha}</tex>,
 +
*<tex>\mathtt{list\left<list\left<A\right>\right>}</tex> <tex>\mathtt{ans}</tex>  {{---}} список, содержащий все сгенерированные объекты в нужном порядке.
  
Gen(p, K)
+
  '''list<A>''' genObj('''list<A>''' K, '''int''' depth, '''list<list<A>>''' ans):
  if p = <требуемый размер объекта>
+
    '''if''' depth == len                                <font color=green> // если сформирован объект нужного размера, то возвращаем его  </font>  
     <выводим> K
+
     ans.push_back(K)                              <font color=green>// записываем объект K в ответ </font>
   else
+
   '''else'''
      for <все w из алфавита на котором строится K>
+
    '''for''' i = 1 '''to''' n                       
         if (K + w) = <корректный префикс требуемого объекта>
+
         '''if''' к объекту К можно добавить элемент alpha[i] в конец
          Gen(p + 1, K + w)
+
          genObj(K ++ alpha[i], depth + 1, ans)   <font color=green> // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса </font>
  
 
==== Генерация с помощью процедуры получения следующего объекта ====
 
==== Генерация с помощью процедуры получения следующего объекта ====
  
Составляем первый объект - <tex>K_1</tex>, для него [[Получение следующего объекта|получаем следующий объект]] - <tex>K_2</tex>, для <tex>K_2</tex> получаем <tex>K_3</tex>, далее действуем также, для <tex>K_i</tex> получая <tex>K_i</tex><tex>_+</tex><tex>_1</tex> объект, пока не получим последний объект <tex>K_n</tex>.
+
Составляем первый объект {{---}} <tex>K_1</tex>, для него [[Получение следующего объекта|получаем следующий объект]] {{---}} <tex>K_2</tex>, для <tex>K_2</tex> получаем <tex>K_3</tex>, далее действуем также, для <tex>K_i</tex> получая <tex>K_i</tex><tex>_+</tex><tex>_1</tex> объект, пока не получим последний объект <tex>K_n</tex>.
  
 
== Примеры ==
 
== Примеры ==
  
==== Пример генерации сочетаний из N элементов по K в лексикографическом порядке ====
+
==== Пример генерации сочетаний из N элементов по M в лексикографическом порядке ====
  
Первым сочетанием, очевидно, будет сочетание <tex>(1,2,...,K)</tex>. Научимся для текущего сочетания находить лексикографически следующее. Для этого в текущем сочетании найдём самый правый элемент, не достигший ещё своего наибольшего значения; тогда увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения.
+
Данный алгоритм генерирует все сочетания из <tex>n</tex> элементов по <tex>m</tex>.
  
Пусть <tex>next_combination (a, n)</tex> - процедура генерирования, где <tex>a</tex> - текущее сочетание, <tex>n</tex> - количество элементов.
+
*<tex>\mathtt{genChooses(k, l)}</tex> {{---}} процедура генерирования,
 +
*<tex>\mathtt{list\left<int\right>}</tex> <tex>\mathtt{a}</tex> {{---}} текущее сочетание,
 +
*<tex>\mathtt{k}</tex> {{---}} следующий элемент в сочетании,
 +
*<tex>\mathtt{l}</tex> {{---}} глубина рекурсии,
 +
*<tex>\mathtt{list\left<list\left<int\right>\right>\ ans}</tex> {{---}} все сгенерированные сочетания в нужном порядке.
  
[[Файл:Example123georgy.png]]
+
'''list<int>''' genChooses('''int''' k, '''int''' l, '''list<int>''' a, '''list<list<int>>''' ans):
 +
  '''if''' l == m       
 +
    ans.push_back(a)
 +
  '''else'''
 +
    '''for''' i = k + 1 '''to''' n
 +
      genChooses(i, l + 1, a ++ i, ans)
  
 
==== Пример работы процедуры генерации ====
 
==== Пример работы процедуры генерации ====
  
Иллюстрация работы процедуры генерирования всех перестановок из чисел <tex>1, 2, 3</tex>
+
Иллюстрация работы процедуры генерации <tex dpi=150>\binom {4} {2} </tex>
 +
 
 +
[[Файл:1211.png]]
 +
 
 +
==См. также==
 +
* [[Получение номера по объекту]]
 +
* [[Получение объекта по номеру]]
 +
 
 +
== Источники информации ==
 +
* [http://ru.wikipedia.org/wiki/Перечисление_(комбинаторика) Википедия — Перечисление (комбинаторика)]
 +
* [http://rain.ifmo.ru/cat/view.php/ Дискретная математика — Алгоритмы]
 +
* [http://algolist.ru/maths/combinat/ AlgoList — Комбинаторика и переборные задачи]
 +
* [http://e-maxx.ru/algo/ MAXimal :: Комбинаторика]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
  
[[Файл:Gen_Perm.png]]
+
[[Категория: Комбинаторика ]]
  
== Ссылки ==
+
[[Категория: Генерация комбинаторных объектов]]
* [http://ru.wikipedia.org/wiki/Перечисление_(комбинаторика) Перечисление (комбинаторика)]
 
* [http://rain.ifmo.ru/cat/view.php/ ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ]
 
* [http://algolist.ru/maths/combinat/ Комбинаторика и переборные задачи]
 
* [http://e-maxx.ru/algo/ Комбинаторика]
 

Текущая версия на 19:21, 4 сентября 2022

Комбинаторные объекты сгенерированы в лексикографическом порядке , если для любых [math] i\lt j [/math] выполняется неравенство [math] S_i\lt S_j [/math], где [math] S_i [/math] и [math] S_j [/math] комбинаторные объекты с номерами [math] i [/math] и [math] j [/math].

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

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

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

  • [math]\mathtt{genObj(K, ␣␣depth)}[/math] — процедура генерирования,
  • [math]\mathtt{depth}[/math] — глубина рекурсии,
  • [math]\mathtt{list\left\lt A\right\gt }[/math] [math]\mathtt{K}[/math] — текущий комбинаторный объект,
  • [math]\mathtt{len}[/math] — требуемый размер объекта,
  • [math]\mathtt{list\left\lt A\right\gt }[/math] [math]\mathtt{alpha}[/math] — все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке,
  • [math]\mathtt{n}[/math] — размер [math]\mathtt{alpha}[/math],
  • [math]\mathtt{list\left\lt list\left\lt A\right\gt \right\gt }[/math] [math]\mathtt{ans}[/math] — список, содержащий все сгенерированные объекты в нужном порядке.
 list<A> genObj(list<A> K, int depth, list<list<A>> ans):
   if depth == len                                 // если сформирован объект нужного размера, то возвращаем его    
    ans.push_back(K)                              // записываем объект K в ответ 
  else
    for i = 1 to n                        
       if к объекту К можно добавить элемент alpha[i] в конец
         genObj(K ++ alpha[i], depth + 1, ans)    // добавляем alpha[i] в конец и вызываем функцию genObj от нового полученного префикса 

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

Составляем первый объект — [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]\mathtt{genChooses(k, l)}[/math] — процедура генерирования,
  • [math]\mathtt{list\left\lt int\right\gt }[/math] [math]\mathtt{a}[/math] — текущее сочетание,
  • [math]\mathtt{k}[/math] — следующий элемент в сочетании,
  • [math]\mathtt{l}[/math] — глубина рекурсии,
  • [math]\mathtt{list\left\lt list\left\lt int\right\gt \right\gt \ ans}[/math] — все сгенерированные сочетания в нужном порядке.
list<int> genChooses(int k, int l, list<int> a, list<list<int>> ans):
  if l == m        
    ans.push_back(a)
  else
    for i = k + 1 to n
      genChooses(i, l + 1, a ++ i, ans)

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

Иллюстрация работы процедуры генерации [math]\binom {4} {2} [/math]

1211.png

См. также

Источники информации