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

  •  
      Здесь собраны задачи, в которых требуется получить один за другим все элементы некоторого множества.

       

      2.1.1. Напечатать все последовательности длины k из чисел 1..n.

      Решение. Будем печатать их в лексикографическом порядке (последовательность 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-ичной системе счисления.

      2.1.2. В предложенном алгоритме используется сравнение двух массивов x <> last. Устранить его, добавив булевскую переменную l и включив в инвариант соотношение l <=> последовательность x - последняя.

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

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

      2.1.4. Напечатать все последовательности из k положительных целых чисел, у которых i-ый член не превосходит i.

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

10.06.2016. 2.3. Подмножества
  2.3.1. Перечислить все k-элементные подмножества множества {1..n}. Решение. Будем представлять каждое подмножество последовательностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц.…
10.06.2016. 2.4. Разбиения
  2.4.1. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1,…
10.06.2016. 2.5. Коды Грея и аналогичные задачи
Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый следующий минимально отличался от предыдущего. Рассмотрим несколько задач такого рода. 2.5.1. Перечислить все последовательности…
10.06.2016. 2.6. Несколько замечаний
  Посмотрим ещё раз на использованные нами приёмы. Вначале удавалось решить задачу по такой схеме: определяем порядок на подлежащих перечислению объектах и явно описываем процедуру перехода от данного…
10.06.2016. 2.7. Подсчет количеств
  Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя…