Разбиения

$\scriptstyle{\blacktriangleright}$ 2.4.1. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)

Решение. Договоримся, что (1) в разбиениях слагаемые идут в невозрастающем порядке, (2) сами разбиения мы перечисляем в лексикографическом порядке. Разбиение храним в начале массива x[1]..x[n], при этом количество входящих в него чисел обозначим k. В начале x[1]=...=x[n]=1, k=n, в конце x[1]=n, k=1.

В каком случае x[s] можно увеличить, не меняя предыдущих? Во-первых, должно быть x[s-1]>x[s] или s=1. Во-вторых, s должно быть не последним элементом (увеличение s надо компенсировать уменьшением следующих). Увеличив s, все следующие элементы надо взять минимально возможными.

        s := k - 1;
        while not ((s=1) or (x[s-1] > x[s])) do begin
        | s := s-1;
        end;
        {s - подлежащее увеличению слагаемое}
        x [s] := x[s] + 1;
        sum := 0;
        for i := s+1 to k do begin
        | sum := sum + x[i];
        end;
        {sum - сумма членов, стоявших после x[s]}
        for i := 1 to sum-1 do begin
        | x [s+i] := 1;
        end;
        k := s+sum-1;`

$\scriptstyle{\blacktriangleright}$ 2.4.2. Представляя по-прежнему разбиения как невозрастающие последовательности, перечислить их в порядке, обратном лексикографическому (для n=4, например, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1).

[Указание. Уменьшать можно первый справа член, не равный 1; найдя его, уменьшим на 1, а следующие возьмем максимально возможными (равными ему, пока хватает суммы, а последний -- сколько останется).] $\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 2.4.3. Представляя разбиения как неубывающие последовательности, перечислить их в лексикографическом порядке. Пример для n=4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4.

[Указание. Последний член увеличить нельзя, а предпоследний -- можно; если после увеличения на 1 предпоследнего члена за счет последнего нарушится возрастание, то из двух членов надо сделать один, если нет, то последний член надо разбить на слагаемые, равные предыдущему, и остаток, не меньший его.] $\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 2.4.4. Представляя разбиения как неубывающие последовательности, перечислить их в порядке, обратном лексикографическому. Пример для n=4: 4, 2+2, 1+3, 1+1+2, 1+1+1+1.

[Указание. Чтобы элемент x[s] можно было уменьшить, необходимо, чтобы s=1 или x[s-1]<x[s]. Если x[s] не последний, то этого и достаточно. Если он последний, то нужно, чтобы $\hbox{\tt x[s-1]}\leqslant\lfloor\hbox{\tt x[s]/2}\rfloor$ или s=1. (Здесь $\lfloor\alpha\rfloor$ обозначает целую часть $\alpha$ .)] $\blacktriangleleft$

pvv
1/8/1999