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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример генерации сочетаний из N элементов по M в лексикографическом порядке)
(Пример генерации сочетаний из N элементов по M в лексикографическом порядке)
Строка 29: Строка 29:
 
Пусть <tex>gen(k, l)</tex> {{---}} процедура генерирования, где <tex>a</tex> {{---}} текущее сочетание, <tex>k</tex> {{---}} следующий элемент в сочетании,      <tex>l</tex> {{---}} глубина рекурсии.
 
Пусть <tex>gen(k, l)</tex> {{---}} процедура генерирования, где <tex>a</tex> {{---}} текущее сочетание, <tex>k</tex> {{---}} следующий элемент в сочетании,      <tex>l</tex> {{---}} глубина рекурсии.
  
  procedure gen(k, l);
+
  gen(k, l);
begin
 
 
     a[l] = k;
 
     a[l] = k;
 
     if l = m then <проверка на требуемый размер объекта>
 
     if l = m then <проверка на требуемый размер объекта>
Строка 37: Строка 36:
 
         writeln;
 
         writeln;
 
     end else for i = k + 1 to n do rec(i, l + 1);
 
     end else for i = k + 1 to n do rec(i, l + 1);
end;
 
  
 
==== Пример работы процедуры генерации ====
 
==== Пример работы процедуры генерации ====

Версия 15:08, 15 декабря 2011

Определение

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

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

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

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

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

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

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

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

gen(k, l);
    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);

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

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

Imagesperes.jpg

Ссылки