Размещения с повторениями


$\scriptstyle{\blacktriangleright}$ 2.1.1. Напечатать все последовательности длины k из чисел 1..n. $\scriptstyle\blacktriangleleft$

 

Решение. Будем печатать их в лексикографическом порядке (последовательность a предшествует последовательности b, если для некоторого s их начальные отрезки длины s равны, а (s+1)-ый член последовательности a меньше). Первой будет последовательность <1,1,...,1>, последней -- последовательность <n,n,...,n>. Будем хранить последнюю напечатанную последовательность в массиве x[1]..x[k]. 
        ...x[1]...x[k] положить равными 1
        ...напечатать x
        ...last[1]...last[k] положить равным n
        {напечатаны все до x включительно}
        while x <> last do begin
        | ...x := следующая за x последовательность
        | ...напечатать x
        end;

Опишем, как можно перейти от x к следующей последовательности. Согласно определению, у следующей последовательности первые s членов должны быть такими же, а (s+1)-ый -- больше. Это возможно, если x[s+1] меньше n. Среди таких s нужно выбрать наибольшее (иначе полученная последовательность не будет непосредственно следующей). Соответствующее x[s+1] нужно увеличить на 1. Итак, надо, двигаясь с конца последовательности, найти самый правый член, меньший n (он найдется, т. к. по предположению x<>last), увеличить его на 1, а идущие за ним члены положить равными 1. 

        p:=k;
        while not (x[p] < n) do begin
        | p := p-1;
        end;
        {x[p] < n, x[p+1] =...= x[k] = n}
        x[p] := x[p] + 1;
        for i := p+1 to k do begin
        | x[i]:=1;
        end;`

Замечание. Если членами последовательности считать числа не от 1 до n, а от 0 до n-1, то переход к следующему соответствует прибавлению единицы в n-ичной системе счисления.


$\scriptstyle{\blacktriangleright}$ 2.1.2. В предложенном алгоритме используется сравнение двух массивов (x <> last). Устранить его, добавив булевскую переменную l и включив в инвариант соотношение

l $\iff$ последовательность x -- последняя.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 2.1.3. Напечатать все подмножества множества 1...k.

 

Решение. Подмножества находятся во взаимно однозначном соответствии с последовательностями нулей и единиц длины k.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 2.1.4. Напечатать все последовательности положительных целых чисел длины k, у которых i-ый член не превосходит i.$\scriptstyle\blacktriangleleft$


pvv
1/8/1999