2.4. Разбиения

  •  
      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;

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

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

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

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

      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] не последний, то этого и достаточно. Если он последний, то нужно, чтобы x[s-1] <= (целая часть (x[s]/2)) или s=1.

Другие записи

10.06.2016. 2.1. Размещения с повторениями
  Здесь собраны задачи, в которых требуется получить один за другим все элементы некоторого множества.   2.1.1. Напечатать все последовательности длины k из чисел 1..n. Решение. Будем печатать…
10.06.2016. 2.5. Коды Грея и аналогичные задачи
Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый следующий минимально отличался от предыдущего. Рассмотрим несколько задач такого рода. 2.5.1. Перечислить все последовательности…
10.06.2016. 2.6. Несколько замечаний
  Посмотрим ещё раз на использованные нами приёмы. Вначале удавалось решить задачу по такой схеме: определяем порядок на подлежащих перечислению объектах и явно описываем процедуру перехода от данного…
10.06.2016. 2.7. Подсчет количеств
  Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя…