индекс пермутации, задачка на комбинаторику Опции

[Bard]

нам учитель вчера задал такую задачку :
задается N и сама пермутация длины N. требуеться найти индекс этой пермутации в N!

пример:
4
2 3 1 4
ответ: 17

пример:
5
5 4 3 2 1
ответ: 120

и т.д

помогите пожалуйста с реализацией алгоритма...

спс за внимание(заранее)

[samec]

есть алгоритм генерации всех перестановок N-элементного множества в лексикографическом порядке. Посмотреть можно тут: Перестановки
Так вот:
1) заводим переменную, для подсчёта перестановок.
2) генерируем очередную перестановку(при этом увеличиваем индекс нашей переменной)
3) сравниваем её со своей (заданной) пермутацией, и если одно и то же, то решением задачи будет значение нашей переменной
вродеб всё.

Сообщение отредактировано: samec - 24.04.2007 10:05

[Bard]

спасибо за помощь но этот путь я уже давно хотел предпринять но учитель сказал что надо метод попроще найти ...твой алгоритм занимает очен много времени

кстати N<100

[volvo]

АлгоЛист -> Операции с перестановками (см. PermutationNum)

[Bard]

а нету ли чего нибудь на паскале???

[volvo]

Дельфийский код переносится на Паскаль практически один в один...

Добавлено через 2 мин.
Я, кстати уже выкладывал код функции PermutationNum, который отрабатывает в Турбо Паскале здесь: Число

[Bard]

Вот так попробуй:

function Fact(n: integer): longint;
var
  i: integer;
  T: longint;
begin
  T := 1;
  for i := 1 to n do T := T * i;
  Fact := T;
end;

function PermutationNum(const A : array of integer; N : Integer): longint;
var
  T, i, j: integer;
  F: longint;
  theResult: longint;
begin
  if N <= 0 then begin
    PermutationNum := 0; Exit;
  end;

  I:=1;
  while I <= N do begin

    if (A[I]<1) or (A[I]>N) then begin
      PermutationNum := 0; Exit;
    end;
    Inc(I);

  end;

  theResult := 0;
  F := 1;
  I := 1;
  while I <= N do begin
    F := F*I;
    Inc(I);
  end;

  I := 1;
  while I <= N-1 do begin
    F := F div (N+1-I);
    T := A[I]-1;
    J := 1;
    while J <= I-1 do begin
      if A[J]<A[I] then begin
        T := T-1;
      end;
      Inc(J);
    end;
    theResult := theResult + F*T;
    Inc(I);
  end;
  theResult := theResult + 1;
  PermutationNum := theResult;
end;

const
  n: integer = 3;
var
  arr: array[0 .. 8] of integer;
  s: string;
  i: integer;
  p, total: longint;

begin
  write('n = '); readln(n);
  write('number[', n, ' chars] = '); readln(s);

  arr[0] := 0;
  for i := 1 to n do arr[i] := ord(s[i]) - ord('0');

  p := PermutationNum(arr, n);
  total := Fact(n);
  writeln(total - p);
end.

(вводишь сначала n - не больше 8, потом в виде строки само число из n цифр...)

Volvo, если тебя не затруднит подскажи что делает эта прога???
при n=5 и s='12345' ответ=119 ...
почему это так?

Добавлено через 6 мин.
помоему я нашел... надо просто стереть функцию Fact и написать writeln(p); вместо writeln(total-p);...
вот и все... огромное спасибо за помощь Volvo

[volvo]

Ну, да... Там же немного другая задача стояла... Тебе достаточно WriteLn(p) ...