2.2. Перестановки

  •  
      2.2.1. Напечатать все перестановки чисел 1..n (то есть последовательности длины n, в которые каждое из чисел 1..n входит по одному разу).

      Решение. Перестановки будем хранить в массиве x[1],..., x[n] и печатать в лексикографическом порядке. (Первой при этом будет перестановка <1 2...n>, последней - <n...2 1>.) Для составления алгоритма перехода к следующей перестановке зададимся вопросом: в каком случае k-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше k). Мы должны найти наибольшее k, при котором это так, т. е. такое k, что x[k] < x[k+1] > ... ><x[1]...x[n]> x[n]. После этого x[k] нужно увеличить минимальным возможным способом, т. е. найти среди x[k+1], ..., x[n] наименьшее число, большее его. Поменяв x[k] с ним, остается расположить числа с номерами k+1, ..., n так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке.

      Алгоритм перехода к следующей перестановке.
      { <><n...2,1> }
      k:=n-1;
      {последовательность справа от k убывающая: x[k+1] >...> x[n]}
      while x[k] > x[k+1] do begin
      | k:=k-1;
      end;
      {x[k] < x[k+1] > ... > x[n]}
      t:=k+1;
      {t <=n, все члены отрезка x[k+1] > ... > x[t] больше x[k]}
      while (t < n) and (x[t+1] > x[k]) do begin
      | t:=t+1;
      end;
      {x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]}
      ... обменять x[k] и x[t]
      {x[k+1] > ... > x[n]}
      ... переставить участок x[k+1] ... x[n] в обратном порядке

      Замечание. Программа имеет знакомый дефект: если t = n, то x[t+1] не определено.

      2.2.2. Модифицировать алгоритм перехода к следующей перестановке так, чтобы он сам проверял, не является ли данная перестановка последней.

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

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-элементного множества - можно найти, заполняя…