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

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

Решение. Перестановки будем хранить в массиве
x[1]..x[n] и печатать в лексикографическом порядке. (Первой при этом будет перестановка $\langle {\hbox{\tt 1}}\,{\hbox{\tt 2}}\ldots{\hbox{\tt n}}\rangle$ ,последней -- $\langle{\hbox{\tt n}}\ldots{\hbox{\tt 2}}\,{\hbox{\tt 1}}\rangle$ .Для составления алгоритма перехода к следующей перестановке зададимся вопросом: в каком случае k-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (т.е. членов с номерами больше k). Мы должны найти наибольшее k, при котором это так, т.е. такое k, что $\begin{displaymath} \hbox{{\hbox{\tt x[k] < x[k+1] \gt ... \gt x[n]}}}\end{displaymath}$ После этого значение 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] не определено.

pvv
1/8/1999