Генерация перестановки, следующей за данной

Процедура находит перестановку следующую за данной в лексикографическом порядке. Начальная перестановка задается в массиве X, туда же после работы процедуры помещается найденная перестановка. Результат равен истине, если на вход подана перестановка являющаяся последней при лексикографическом упорядочивании. Таким образом чтобы получить все перестановки n чисел надо инициализировать массив X значениями 1, 2, ..., n и последовательно вызывать процедуру до тех пор пока результат не окажется равным истине.

Количество перестановок из n чисел будет равно факториалу числа n.

Если нашли ошибку в алгоритме - сообщите!

Реализации алгоритма на различных языках:

Блоксхемы:

Реализация алгоритма на AlgoPascal:

unit PermutationUnit;

interface
    NextPermutation;
implementation

(*
function NextPermutation(
    n:integer;
    var x:array[1..n] of integer):Boolean;

Процедура находит перестановку следующую за данной в
лексикографическом порядке.  Начальная  перестановка
задается в массиве X, туда же после работы процедуры
помещается найденная перестановка. Результат   равен
истине, если на вход подана перестановка  являющаяся
последней при лексикографическом упорядочивании. Таким
образом чтобы получить все перестановки n - чисел надо
инициализировать массив X значениями 1,2,. . ., n и
последовательно вызывать процедуру до тех пор пока
результат не окажется равным истине.

Количество перестановок из n чисел будет равно факториалу числа n.
*)
function NextPermutation(
    const   n   :   Integer;
    var     x   :   array of Integer):Boolean;
var
    k   :   Integer;
    t   :   Integer;
    y   :   Integer;
begin
    k:=n-1;
    while k>0 do
    begin
        if x[k]<=x[k+1] then
            Break;
        k:=k-1;
    end;
    
    if k<>0 then
    begin
        t:=k+1;
        while t<n do
        begin
            if x[t+1]<=x[k] then
                Break;
            t:=t+1;
        end;
        y:=x[k];
        x[k]:=x[t];
        x[t]:=y;
        t:=0;
        while t<((n-k) div 2) do
        begin
            y:=x[n-t];
            x[n-t]:=x[k+1+t];
            x[k+1+t]:=y;
            t:=t+1
        end;
        Result:=False;
    end
    else
    begin
        Result:=True;
    end;
end;




end.

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU