Получение номера перестановки

Ещё один алгоритм для работы с перестановками. Этот алгоритм позволяет по перестановке чисел от 1 до N получить её номер в списке перестановок, упорядоченных в лексикографическом порядке.

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

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

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

unit PermutationNumUnit;

interface PermutationNum;

implementation

(******************************************************
function PermutationNum(
    N : Integer;
    const A : array [1..N] of Integer):Integer;

процедура   находит порядковый номер перестановок чисел
от 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!
уместилось в разрядную сетку компьютера.
******************************************************)
function PermutationNum(N : Integer; const A : array of Integer):Integer;
var
    T           : Integer;
    I           : Integer;
    J           : Integer;
    F           : Integer;
begin
    Result:=0;
    F:=1;
    for I:=1 to N do
        F:=F*I;

    for I:=1 to N-1 do
    begin
        F:=F div (N+1-I);
        T:=A[I]-1;
        
        for J:=1 to I-1 do
            if A[J]<A[I] then
                T:=T-1;

        Result:=Result+F*T;
    end;
    Result:=Result+1;
end;


end.

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