Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритм

Напечатать все перестановки

Задача. Напечатать все перестановки чисел 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] не определено.
 Похожие публикации: Алгоритм

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]