end;

begin s[m]:=1; G(m-1,h-1);

s[m]:=0; GR(m-1,h)

end

begin {SUBSET2} G(n,k) end.

Комментарий. Процедура GR(m,h) соответствует G^R(m,h). Процедура print служит для вывода генерируемых кодовых слов.

Для дальнейшего анализа алгоритма остановимся подробнее на дереве вызова процедурG и GR.

Пример. n=5, k=3.

G(5,3)

0 1

G(4,3) GR(4,2)

0 1 1 0

G(3,3) GR(3,2) G(3,1) GR(3,2)

1 0 0 1 1 0

G(2,1) GR(2,2) G(2,1) GR(2,0) G(2,1) GR(2,2)

0 1 0 1 0 1

G(1,1) GR(1,0) G(1,1) GR(1,0) G(1,1) GR(1,0)

11100 10110 01110 11010 10011 01011 00111 10101 01101 11001

Из текста программы видно, что рекурсивная структура G(n,k) представляется в виде бинарного дерева. Каждую дугу, ведущую в G(m-1,h) или GR(m-1,h), пометим значением, которое присваивается s[m] перед вызовом этой процедуры. Обозначать мы будем соответственно G(m-1,h)s[m] или GR(m-1,h)s[m]. Каждое кодовое слово может быть составлено из значения, вырабатываемого листом, и пометок дуг, составляющих ветвь от этого листа к корню дерева. Очевидно, что два соседних кодовых слова в G(n,k) могут отличаться только в тех разрядах, которые соответствуют несовпадающим частях их ветвей. Каждая вершина бинарного дерева характеризуется ее уровнем-значением m. При этом является однозначно определенной часть текущего кодового слова - позиции s[m],...,s[n]. Кроме того, число h определяет количество единиц, находящиеся в позициях s[1],...,s[m-1].

Упражнения. 1. Доказать, что листья дерева могут быть помечены (m¹0) G(m,0)1, GR(m,0)1 или G(m,m)0, GR(m,m)0, но не могут с G(m,0)0, GR(m,0)0 или с G(m,m)1, GR(m,m)1.

2. Определить число вызовов процедур G и GR как функцию от n и k. (Указание. Определить число кодовых слов, начало которых состоит из 1,2,...,k единиц, и число слов, начало которых состоит из 1,2,...,n-k нулей.)

3. Определить вычислительную сложность программы SUBSET2.

4. Доказать корректность приведенной программы.

Перейдем к построению итеративного алгоритма генерирования G(n,k). Такой алгоритм должен итеративно моделировать левосторонний[2] обход дерева вызова процедур G и GR. В этом случае моделирование осуществляется за счет перехода от текущего кодового слова к следующему за счет информации о еще не полностью обработанных узлов дерева вызова, лежащих на ветви от листа, соответствующему текущему кодовому слову, до корня дерева - вершины G(n,k). Естественно, информация о таких узлах храниться в стеке обхода дерева. Рассмотрим какую информацию необходимо хранить о каждом из таких узлов в стеке. Прежде всего заметим, что по свойству программы SUBSET2, для каждого узла дерева обхода левой его ветви может соответствовать только вызов процедуры G, а правой - вызов процедуры GR. Поэтому еще не полностью обработанными являются узлы соответствующие вызову процедуры G. Для каждого такого узла в стеке достаточно хранить значение его уровня - m. Так как мы знаем, что последующая обработка этого узла будет связана с преобразованием части кодового слова - разряды s[1],...,s[m], при этом значение h легко вычисляется как число единиц, расположенных в разрядах s[1],...,s[m-1].

Пусть m - значение лежащее на вершине стека обхода дерева вызова. Тогда это значение соответствует некоторому вызову процедуры G(m-1,h), который в свою очередь однозначно определяет узел дерева обхода, лежащий на пути из листа, соответствующего текущему кодовому слову в корень дерева, при этом узел G(m-1,h) является первым узлом типа G, лежащим на этом пути. Непосредственного предка узла G(m-1,h) обозначим G*(m,...). Узел G*(m,...) может соответствовать вызову как процедуре G, так и процедуре GR, при этом для процедуры G s[m] в текущем кодовом слове равно 0, для процедуры GR - 1. Пусть узел GR(m-1,...) непосредственный правый потомок вершины G*(m,...). Тогда путь из корня дерева обхода к листу, соответствующему следующему кодовому слову за текущим в G(n,k), может быть описан как

G(n,k),...,G*(m,...), GR(m-1,..), G(m-2,..),...,G(p,...),

где р - уровень узла следующего кодового слова. Т. е. путь из корня рева обхода к листу соответствующему следующему кодовому слову совпадает на участке G(n,k),..., G*(m,...) с путем к текущему кодовому слову, затем осуществляется переход по правой ветви узла G*(m,...), после чего путь проходит только по левым ветвям узлов дерева.

G(n,k)

G*(m,...)

s[m-1] 1-s[m-1]

G(m-1,h) GR(m-1,...)

1 1

GR(m-2,h-1) G(m-2,...)

(текущее кодовое слово) (следующее кодовое слово)

Таким образом, для перехода к следующему кодовому слову мы должны преобразовать текущее кодовое слово в разрядах 1,...,m, а также занести в стек значения уровней вызова процедуры G - m-2,...,p+1. В преобразовании кодового слова одним из изменяемых разрядов является s[m], а другой может быть вычислен на основе теоремы 4.1по следующей схеме:

случай 1. s[m]=0, h>1, это означает, что первые (m-1) разрядов текущего кодового слова являются последним кодовым словом в G(m-1,h), а начало следующего кодового слова представляет собой первое кодовое слово в G^R(m-1,h-1), т. е.

1^h-210^m-h-110... переходит в 1^h-200^m-h-111...

­ ­

s[m] s[m]

если s[m]=0, h=1, тогда

0^m-210... переходит в 0^m-201...

­ ­

s[m] s[m]

случай 2. s[m]=1, h>0, это означает, что первые (m-1) разрядов текущего кодового слова являются последним кодовым словом в G(m-1,h), а начало следующего кодового слова представляет собой первое кодовое слово в G^R(m-1,h), т. е.

1^h-100^m-h-211... переходит в 1^h-110^m-h-210...

­ ­

s[m] s[m]

если s[m]=1, h=0, тогда

0^m-201. .. переходит в 0^m-210...

­ ­

s[m] s[m]

Таким образом, вторым изменяемым разрядом является

s[h-1], если s[m]=0 и h>1

s[m-1], если s[m]=0 и h=1

s[h], если s[m]=0 и h>1

s[m-1], если s[m]=1 и h=0.

Нам осталось установить только значение параметра p, от которого зависит число новых узлов дерева, с не пройденными правыми ветвями.

Если h=0 или h=m-1, то в стек никакие новые узлы не добавляются, поскольку узел G(m-1,h) является листом, однако для последующих преобразований h должно быть изменено на h+1. С другой стороны, в случае h¹0 и h¹m-1 мы должны включить в стек узлы m-1 ,m-2,. . ., h+1, за исключением того случая, когда s[m-2]=...=s[1]=0; в этом же случае в стек включается только m-1. Значение h должно быть вычислено заново, и, так как среди s[m-1], s[m-2],...,s[h+1] единицей может быть только s[m-1], мы можем h вычислить как h-s[m-1]. Если при этом h становиться равным 0, мы должны иметь s[m-2]=...=s[1]=0.

На основе этих рассуждений строится следующая программа:

program subset3;

const n= ; k= ; n1= ; n2= ; {n1=n+1, n2=n+2}

var i,m,h:integer;

s:array[1..n1] of 0..1; {генерируемое кодовое слово}

t:array[1..n1] of 1..n2; { стек узлов}