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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример генерации сочетаний из N элементов по M в лексикографическом порядке)
(Пример генерации сочетаний из N элементов по M в лексикографическом порядке)
Строка 41: Строка 41:
 
*<tex>\mathtt{list{<}list{<}int{>}{>}\ ans}</tex> {{---}} все сгенерированные сочетания в нужном порядке.
 
*<tex>\mathtt{list{<}list{<}int{>}{>}\ ans}</tex> {{---}} все сгенерированные сочетания в нужном порядке.
  
  '''list<int>''' genChooses('''int''' k, '''int''' l, '''int''' []a)
+
  '''list<int>''' genChooses('''int''' k, '''int''' l, '''int[]''' a)
 
   a[l] = k
 
   a[l] = k
 
   '''if''' l == m         
 
   '''if''' l == m         

Версия 16:21, 2 января 2015

Комбинаторные объекты сгенерированы в лексикографическом порядке , если для любых [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{\lt }A{\gt }}[/math] [math]\mathtt{K}[/math] — текущий комбинаторный объект,
  • [math]\mathtt{len}[/math] — требуемый размер объекта,
  • [math]\mathtt{list{\lt }A{\gt }}[/math] [math]\mathtt{alpha}[/math] — все возможные элементы комбинаторного объекта, отсортированные в лексикографическом порядке,
  • [math]\mathtt{n}[/math] — размер [math]\mathtt{alpha}[/math],
  • [math]\mathtt{list{\lt }list{\lt }A{\gt }{\gt }}[/math] [math]\mathtt{ans}[/math] — список, содержащий все сгенерированные объекты в нужном порядке.


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

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

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

4 2 s.png

См. также

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