Подмножество, содержащее к элементов заданного множества А из n элементов (k£n), обычно называют K-подмножествами просто K-множествами. Для представления K-подмножеств, наряду с представлением в виде n-последовательностей нулей и единиц, которое обычно применяют только для хранения в упакованном виде, часто используется представление в виде K-кортежей натуральных чисел. При этом каждый кортеж считается упорядоченным, например, в порядке возрастания. Это связано с тем, что чаще k£n/2. (Так как K-множество и его дополнение однозначно связаны, и поставленную перед пользователем задачу удается переформулировать, используя либо K-множество, либо его дополнение.) Поэтому при хранении K-множеств в виде n-последовательностей нулей и единиц не менее половины из них являются нулями. При хранении K-кортежами могут, например, указываться порядковые номера элементов, входящих в K-множество.
Пример. Множеству (0,0,0,0,1,1,0,1,1,0,0) соответствует кортеж (5,6,8,9).
Перейдем теперь к алгоритму генерирования K-подмножеств в лексикографическом порядке. Прежде всего дадим определение лексикографической упорядоченности в терминах K-кортежей.
Определение. Множество (а1,...,аk), a1<...<ak, предшествует множеству (b1,...,bk), b1<...<bk, если существует i, 1£i£k, такое, что для любого j, j<i, aj=bj, ai<bi.
Упражнение. Доказать, что это определение эквивалентно определению лексикографической упорядоченности из п.3.1.
Первым в лексикографическом порядке является кортеж (1,...,k), а последним - (n-k+1,...,n). Пусть (а1,...,аk) не совпадает с последним кортежем генерации, тогда непосредственно следующим за ним является (b1,...,bk) = (а1,...,ap-1,ap+1,ap+2,...,ap+k-p+1), где р=max(i : ai<n-k+1).При этом, если (b1,...,bk) не последний, то следующий за ним выглядит так: (b1,...,br-1,br+1,br+2,...,br+k-r+1), где r=p-1, если bk=n, и k, если bk<n.
Пример. Генерации K- подмножеств в лексикографическом порядке. n=5, k=2.
1.(1,2) 5.(2,3) 8.(3,4) 10.(4,5)
p=2 p=2 p=2
2.(1,3) 6.(2,4) 9.(3,5)
p=2 p=2 p=1
3.(1,4) 7.(2,5)
p=2 p=1
4.(1,5)
p=1
Это приводит к следующему алгоритму на языке Паскаль:
program SUBSET1;
const n= ; k= ; (k<=n)
var s : array[1..k] of 1..n;
i,p : integer;
begin
for i:=1 to k do
{1} s[i]:=i; {задание первого K-множества}
p:=1;
while p>=1 do
begin
for i:=1 to k do write(s[i]); writeln;
{вывод очередного K-множества}
if s[k]=n then p:=p-1 else p:=k;
if p>=1 then
begin
s[p]:=s[p]+1;
for i:=p+1 to k do
{3} s[i]:=s[i-1]+1
end
end
end.
Оценим вычислительную сложность программы. Заметим, что оператор сроки {1} исполняется k раз; строки {2} - Cраз; а строки {3} - C-1+ C-1+....+ C-1 раз, равное C-k-1. То есть вычислительная сложность программы O(C). Учитывая, что C= C×[(n+1)/(n-k+1)] и C×[k/(n-k+1)], получаем, что алгоритм линеен, за исключением случаев, когда k=n-o(n). В этом случае алгоритм можно применить для порождения (n-k)-подмножеств, с последующим переходом к их дополнению.
Упражнение. Написать вариант программы SUBSET1 для K-подмножеств, представленных n-последовательностями нулей и единиц. Оценить вычислительную сложность построенной программы.
6.1Генерация K-подмножеств заменой одного элемента.
Для того чтобы убедиться в том, что подобные генерации существуют, рассмотрим некоторые свойства симметрично-отраженных кодов Грея.
Обозначение. Пусть a-некоторая цепочка над алфавитом Х. Тогда am, где m - целое неотрицательное число, обозначает конкатенацию m раз цепочки a.
Пример. Х={a,b,c} (ab)3=ababab ab3=abbb.
В дальнейшем симметрично-отраженный код Грея n-го порядка, генерируемый программой SET2, будем обозначать G(n). Естественно, что любое кодовое слово из G(n) является цепочкой длины n над {0,1}. Последовательности кодовых слов из G(n), содержащие k единиц и упорядоченные соответственно с их генерацией программой SET2, будем обозначать G(n,k). Последовательности, в которых кодовые слова располагаются в обратном порядке по отношению к G(n) или G(n,k), будем обозначать GR(n) и GR(n,k) соответственно.
Теорема 4.1. Первым кодовым словом в G(n) ровно k единицами будет 1k0n-k, а последним - 1k-10n-k1 и 0n, если k=0.
Доказательство проводится индукцией по n, при n=1 - очевидно. Пусть теорема справедлива для i£n и любых k, покажем, что теорема справедлива для n+1 и всех k. В терминах G(n) соотношение {1} из п.3.2 может быть записано как G(n+1)=G(n)0;GR(n)1, поэтому первое кодовое слово с k³0 единицами (кроме k=n+1) есть первое кодовое слово в G(n) с приписанным справа нулем. Иными словами, 1k0n+1-k, как и требовалось. Аналогично последнее кодовое слово с k³1 единицами в G(n) c приписанной справа единицей - это 1k-10n-k+11, как и требовалось. В случае k=n+1 единственным словом в G(n+1), содержащим n+1 единицу, является 1n+1.
Теорема 4.2. Соседние кодовые слова в G(n,k) различаются ровно в двух разрядах.
Доказательство проводится индукцией по n. Теорема, очевидно, справедлива для n=1, поскольку k=0, либо k=1. Предположим, что теорема верна для n и всех k, 0£k£n. Покажем, что она верна для n+1 и любого k, 0£k£n+1. Если k=0 или k=n+1, она справедлива, так как G(n+1) содержит только одно соответствующее кодовое слово. Для 1£k£n теорема выполняется по индукционному предположению, если кодовые слова оба либо в G(n)0 либо GR(n)1. Таким образом, требуется только рассмотреть, на сколько разрядов отличается последнее кодовое слово с k единицами в G(n)0 от первого кодового слова с k единицами в GR(n)1. Из предыдущей теоремы следует, что эти слова имеют вид: при k=1 0n-110 и 0n1, при k>1 1k-210n-k10 и 1k-200n-k11 соответственно.
Следствие. Последовательность кодовых слов G(n,k), n³k³0, можно определить следующей рекурсией:
G(n,k)=G(n-1,k); GR(n-1,k-1)1 и G(n,0)=0n, G(n,n)=1n. {2}
В самом деле, это определение действительно задает последовательность, совпадающую с той, которая получается удалением из G(n) всех кодовых слов с числом единиц, не равным k.
Рекурсивное определение {2} приводит к следующей программе генерации кодовых слов G(n,k) на языке Паскаль.
program subset2;
const n= ; k= ; {0<k<=n}
var i : integer;
s:array[1..n] of 0..1;
procedure print (m,h:integer);
begin
if h<>0 then h:=1;
for i:=1 to m do s[i]:=h;
for i:=1 to n do write(s[i]);
end;
procedure GR(m,h:integer); forward;
procedure G(m,h:integer);
begin
if (h=0) or (m=h) then print(m,h)
else
begin s[m]:=0; G(m-1,h);
s[m]:=1; GR(m-1,h-1)
end
end;
procedure GR;
begin
if (h=0) or (m=h) then print(m,h)
else
begin s[m]:=1; G(m-1,h-1);
s[m]:=0; GR(m-1,h)
end
end;
begin {SUBSET2} G(n,k) end.
Комментарий. Процедура GR(m,h) соответствует GR(m,h). Процедура print служит для вывода генерируемых кодовых слов.
Для дальнейшего анализа алгоритма остановимся подробнее на дереве вызова процедурG и GR.
Из текста программы видно, что рекурсивная структура 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,...) с путем к текущему кодовому слову, затем осуществляется переход по правой ветви узла 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), а начало следующего кодового слова представляет собой первое кодовое слово в GR(m-1,h-1), т. е.
1h-210m-h-110... переходит в 1h-200m-h-111...
s[m] s[m]
если s[m]=0, h=1, тогда
0m-210... переходит в 0m-201...
s[m] s[m]
случай 2. s[m]=1, h>0, это означает, что первые (m-1) разрядов текущего кодового слова являются последним кодовым словом в G(m-1,h), а начало следующего кодового слова представляет собой первое кодовое слово в GR(m-1,h), т. е.
1h-100m-h-211... переходит в 1h-110m-h-210...
s[m] s[m]
если s[m]=1, h=0, тогда
0m-201. .. переходит в 0m-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.
На основе этих рассуждений строится следующая программа:
раз; а строки {3} - C
-1+....+ C
-1 раз, равное C
-k-1. То есть вычислительная сложность программы O(C
×[(n+1)/(n-k+1)] и C
×[k/(n-k+1)], получаем, что алгоритм линеен, за исключением случаев, когда k=n-o(n). В этом случае алгоритм можно применить для порождения (n-k)-подмножеств, с последующим переходом к их дополнению.
G(5,3)
G*(m,...)
1 1
