Подмножества

$\scriptstyle{\blacktriangleright}$ 2.3.1. Перечислить все k-элементные подмножества множества 1..n.

Решение. Будем представлять каждое подмножество последовательностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц. (Другой способ представления разберем позже.) Такие последовательности упорядочим лексикографически (см. выше). Очевидный способ решения задачи -- перебирать все последовательности как раньше, а затем отбирать среди них те, у которых k единиц -- мы отбросим, считая его неэкономичным (число последовательностей с k единицами может быть много меньше числа всех последовательностей). Будем искать такой алгоритм, чтобы получение очередной последовательности требовало не более Cn действий.

В каком случае s-ый член последовательности можно увеличить, не меняя предыдущие? Если x[s] меняется с 0 на 1, то для сохранения общего числа единиц нужно справа от х[s] заменить 1 на 0. Для этого надо, чтобы справа от x[s] единицы были. Если мы хотим перейти к непосредственно следующему, то x[s] должен быть первым справа нулем, за которым стоят единицы. Легко видеть, что х[s+1]=1 (иначе х[s] не первый). Таким образом надо искать наибольшее s, для которого х[s]=0, x[s+1]=1:

$\begin{displaymath} \hbox{\tt x}\, { \setlength {\tabcolsep}{.2em} \begin{tabu... ...ss }}& \hbox{\tt 1..1} & \hbox{\tt 0..0}\\ \hline\end{tabular}}\end{displaymath}$

За х[s+1] могут идти еще несколько единиц, а после них несколько нулей. Заменив х[s] на 1, надо выбрать идущие за ним члены так, чтобы последовательность была бы минимальна с точки зрения нашего порядка, т.е. чтобы сначала шли нули, а потом единицы. Вот что получается:

первая последовательность: 0..01..1 (n-k нулей, k единиц)

последняя последовательность: 1..10..0 (k единиц, n-k нулей)

алгоритм перехода к следующей за х[1]..x[n] последовательности (предполагаем, что она есть):

     s := n - 1;
     while not ((x[s]=0) and (x[s+1]=1)) do begin
     | s := s - 1;
     end;
     {s - член, подлежащий изменению с 0 на 1}
     num:=0;
     for k := s to n do begin
     | num := num + x[k];
     end;
     {num - число единиц на участке x[s]...x[n],
      число нулей равно (длина - число единиц),
      т. е. (n-s+1) - num}
     x[s]:=1;
     for k := s+1 to n-num+1 do begin
     | x[k] := 0;
     end;
     {осталось поместить num-1 единиц в конце}
     for k := n-num+2 to n do begin
     | x[k]:=1;
     end;`

Другой способ представления подмножеств -- это перечисление их элементов. Чтобы каждое подмножество имело ровно одно представление, договоримся перечислять элементы в возрастающем порядке. Приходим к такой задаче.

$\scriptstyle{\blacktriangleright}$ 2.3.2. Перечислить все возрастающие последовательности длины k из чисел 1..n в лексикографическом порядке. (Пример: при n=5, k=2 получаем: 12 13 14 15 23 24 25 34 35 45.)

Решение. Минимальной будет последовательность
$\langle{\hbox{\tt 1}}\,{\hbox{\tt 2}}\ldots{\hbox{\tt k}}\rangle$ ;максимальной -- $\langle{\hbox{\tt (n-k+1)}}\ldots{\hbox{\tt (n-1)}}\,{\hbox{\tt n}}\rangle$ .В каком случае s-ый член последовательности можно увеличить? Ответ: если он меньше n-k+s. После увеличения s-го элемента все следующие должны возрастать с шагом 1. Получаем такой алгоритм перехода к следующему:

        s:=n;
        while not (x[s] < n-k+s) do begin
        | s:=s-1;
        end;
        {s - номер элемента, подлежащего увеличению};
        x[s] := x[s]+1;
        for i := s+1 to n do begin
        | x[i] := x[i-1]+1;
        end;`

$\scriptstyle{\blacktriangleright}$ 2.3.3. Пусть мы решили представлять k-элементные подмножества множества 1..n убывающими последовательностями длины k, упорядоченными по-прежнему лексикографически. (Пример: 21 31 32 41 42 43 51 52 53 54.) Как выглядит тогда алгоритм перехода к следующей?

Ответ. Ищем наибольшее s, для которого $\begin{displaymath} {\hbox{\tt х[s+1]+1 < x[s]}}.\end{displaymath}$ (Если такого s нет, полагаем s=0.) Увеличив x[s+1] на 1, кладем остальные минимально возможными (x[t]=k+1-t для t>s). $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 2.3.4. Решить две предыдущие задачи, заменив лексикографический порядок на обратный (раньше идут те, которые больше в лексикографическом порядке). $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 2.3.5. Перечислить все вложения (функции, переводящие разные элементы в разные) множества 1..k в 1..n (предполагается, что kn). Порождение очередного элемента должно требовать не более Ck действий.

[Указание. Эта задача может быть сведена к перечислению подмножеств и перестановок элементов каждого подмножества.] $\blacktriangleleft$

pvv
1/8/1999