Получить все перестановки чисел 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[n]. После  этого  x[k]  нужно  увеличить  минимальным  возможным способом, т. е. найти среди x[k+1], ..., x[n] наименьшее число, большее его. Поменяв x[k] с ним, остается расположить числа с номерами k+1, ..., n  так,  чтобы  перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке.

Алгоритм перехода к следующей перестановке.

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

---