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.2. Перестановки
  2.2.1. Напечатать все перестановки чисел 1..n (то есть последовательности длины n, в которые каждое из чисел 1..n входит по одному разу). Решение. Перестановки будем хранить в массиве x[1],...,…