Задача 98824

Тема:    [ Нерекурсивная генерация объектов ]

Сложность: 3 Классы:

Условие

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

Решение

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

x[k] < x[k+1] >...> x[n]

После этого значение x[k] нужно увеличить минимальным возможным способом,  —е найти среди x[k+1]..x[n] наименьшее число, большее его. Поменяв x[k] с ним, остаётся расположить числа с номерами k+1..n так, чтобы перестановка была наименьшей,  —е в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке. Алгоритм перехода к следующей перестановке:

      {<x[1]...x[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] не определено.

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	2
Название	Порождение комбинаторных объектов
параграф
Номер	2
Название	Перестановки
задача
Номер	2.2.1