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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Алгоритм построения)
(→‎Пример генерации сочетаний из N элементов по K в лексикографическом порядке)
Строка 23: Строка 23:
 
== Примеры ==
 
== Примеры ==
  
−
==== Пример генерации сочетаний из N элементов по K в лексикографическом порядке ====
+
==== Пример генерации сочетаний из N элементов по M в лексикографическом порядке ====
  
−
Первым сочетанием, очевидно, будет сочетание <tex>(1,2,...,K)</tex>. Научимся для текущего сочетания находить лексикографически следующее. Для этого в текущем сочетании найдём самый правый элемент, не достигший ещё своего наибольшего значения; тогда увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения.
+
Пусть <tex>gen(k, l)</tex> - процедура генерирования, где <tex>a</tex> - текущее сочетание, <tex>k</tex> - следующий элемент в сочетании,     <tex>l</tex> - глубина рекурсии.
  
−
Пусть <tex>next_combination (a, n)</tex> - процедура генерирования, где <tex>a</tex> - текущее сочетание, <tex>n</tex> - количество элементов.
+
procedure gen(k, l : longint);
−
 
+
var
−
  bool next_combination (vector<int> & a, int n) {
+
    i : longint;
−
int k = (int)a.size();
+
  begin
−
  for (int i=k-1; i>=0; --i)
+
    a[l] := k;
−
          if (a[i] < n-k+i+1) {
+
    if l = m then {объект имеет требуемый размер}
−
                  ++a[i];
+
    begin
−
                  for (int j=i+1; j<k; ++j)
+
        for j := 1 to m do write(a[j], ' '); {выводим текущее сочетание}
−
                          a[j] = a[j-1]+1;
+
        writeln;
−
                  return true;
+
    end else for i := k+1 to n do rec(i, l+1); {перебираем подходящий префикс}
−
          }
+
end;
−
  return false;
 
−
}
 
  
 
==== Пример работы процедуры генерации ====
 
==== Пример работы процедуры генерации ====

Версия 03:10, 8 ноября 2011

Определение

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

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

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

Пусть [math]Gen(p, K)[/math] — процедура генерирования, где [math]p[/math] — глубина рекурсии, [math]K[/math] — комбинаторный объект. 

Gen(p, K)
  if p = <требуемый размер объекта>
    <выводим> K
  else
     for <все w из алфавита на котором строится K>
       if (K + w) = <корректный префикс требуемого объекта>
         Gen(p + 1, K + w)

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

Составляем первый объект — [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]gen(k, l)[/math] - процедура генерирования, где [math]a[/math] - текущее сочетание, [math]k[/math] - следующий элемент в сочетании, [math]l[/math] - глубина рекурсии. 

procedure gen(k, l : longint);
var
    i : longint;
begin
    a[l] := k;
    if l = m then {объект имеет требуемый размер}
    begin
        for j := 1 to m do write(a[j], ' '); {выводим текущее сочетание}
        writeln;
    end else for i := k+1 to n do rec(i, l+1); {перебираем подходящий префикс}
end;

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

Иллюстрация работы процедуры генерирования всех перестановок из чисел [math]1, 2, 3[/math]

Gen Perm.png

Ссылки

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