Генерация перестановки по номеру

Этот алгоритм предназначен для получения перестановки по её номеру (перестановки упорядочены в лексикографическом порядке). В принципе, чтобы получить перестановку с номером K, можно вызвать K раз алгоритм получения следующей перестановки. Если требуется последовательно получать перестановки с номерами от 1 до K, то можно поступить и так, но в случае, когда требуется получить лишь K-ую перестановку, но такой способ крайне неэффективен. Для этого можно использовать специальный алгоритм, который позволяет непосредственно получить искомую перестановку без всяких промежуточных шагов.

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

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

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

unit KthPermutationUnit;

interface KthPermutation;

implementation

(*********************************************
NthPermutation(N : Integer;
    K : Integer;
    out A : array [1..N] of Integer);

процедура находит K-ую из   перестановок чисел
от  1 до N, упорядоченных в лексикографическом
порядке. Перестановки нумеруются от 1 до N!.

Скажем,  для  N  равного  3  существуют шесть
перестановок:
    №1: 1 2 3
    №2: 1 3 2
    №3: 2 1 3
    №4: 2 3 1
    №5: 3 1 2
    №6: 3 2 1

Число N должно быть достаточно    мало,  чтобы
N! уместилось в разрядную сетку компьютера.
*********************************************)
procedure KthPermutation(
    N : Integer;
    K : Integer;
    out A : array of Integer);
var
    Temp        : Integer;
    SelNum      : Integer;
    I           : Integer;
    J           : Integer;
    F           : Integer;
begin
    K:=K-1;
    F:=1;
    SetBounds(A, [1, N]);
    for I:=1 to N do
    begin
        A[I]:=I;
        F:=F*I;
    end;
        
    for I:=1 to N-1 do
    begin
        F:=F div (N+1-I);
        SelNum:=I+(K div F);
        
        Temp:=A[SelNum];
        for J:=SelNum downto I+1 do
            A[J]:=A[J-1];
        A[I]:=Temp;
        
        K:=K mod F;
    end;
end;


end.

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