First = (1,2,…,N), Last = (N,N-1,…,1)
Всего таких перестановок будет N!=N*(N-1)*…*2*1. Для составления алгоритма Next зададимся вопросом: в каком случае i-ый элемент перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).
Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>…>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],…,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,…,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:
procedure Next;
begin
шаг 1: {найти i: X[i]<X[i+1]>X[i+2]>…>X[N]}; Находим наибольший по порядку элемент меньший следующего за ним (выставляем элементы в строку и ищем справа налево
шаг 2: {найти j: X[j]>X[i]>X[j+1]>…>X[N]}; Находим среди элементов следующих за ним число наименьше большее
шаг 3: {обменять X[i] и X[j]};
шаг 4: {X[i+1]>X[i+2]>…>X[N]};
{перевернуть X[i+1],X[i+2],…,X[N]}; устанавливаем порядок возрастания с i+1-го элемента
end;
Например:
Возьмем число — 123
123 Шаг 1. Нашли 2 (i=2) Шаг 2. Нашли 3 (j=3) Шаг 3. 132 Шаг 4. 132 | 132 Шаг 1. Нашли 1 (i=1) Шаг 2. Нашли 2 (j=3) Шаг 3. 231 Шаг 4. 213 | 213 Шаг 1. Нашли 1 (i=2) Шаг 2. Нашли 3 (j=3) Шаг 3. 231 Шаг 4. 231 | 231 Шаг 1. Нашли 2 (i=1) Шаг 2. Нашли 3 (j=2) Шаг 3. 321 Шаг 4. 312 | 312 Шаг 1. Нашли 1 (i=2) Шаг 2. Нашли 2 (j=3) Шаг 3. 321 Шаг 4. 321 |
program Perestanovki;
type Pere=array [byte] of byte;
var N,i,j:byte;
X:Pere;
Yes:boolean;
procedure Next(var X:Pere;var Yes:boolean);
var i:byte;
procedure Swap(var a,b:byte); {обмен переменных}
var c:byte;
begin c:=a;a:=b;b:=c end;
begin
i:=N-1; {поиск начинаем с предпоследнего элемента}
{поиск наибольшего по порядку i}
while (i>0)and(X[i]>X[i+1]) do dec(i); {перебираем варианты не подходящие и как только X[i]<X[i+1] то выходим из цикла }
if i>0 then {если в результате перебора i не стала отрицательным т.е. нашелся вариант, то начинаем искать j иначе присваиваем логической переменной значение False и заканчиваем работу программы}
begin
j:=i+1;
{поиск j}
while (j<N)and(X[j+1]>X[i]) do inc(j);
Swap(X[i],X[j]);
for j:=i+1 to (N+i) div 2 do Swap(X[j],X[N-j+i+1]); {расположение оставшейся части после i в возрастающем порядке}
Yes:=true
end
else Yes:=false
end;
begin
write('N=');readln(N);
for i:=1 to N do X[i]:=i;
repeat
for i:=1 to N do write(X[i]);writeln;
Next(X,Yes)
until not Yes
end.