Помощь - Поиск - Пользователи - Календарь
Полная версия: индекс пермутации
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Bard
нам учитель вчера задал такую задачку unsure.gif :
задается N и сама пермутация длины N. требуеться найти индекс этой пермутации в N!

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

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

и т.д

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

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

кстати N<100 wacko.gif
volvo
АлгоЛист -> Операции с перестановками (см. PermutationNum)
Bard
а нету ли чего нибудь на паскале??? good.gif
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, если тебя не затруднит подскажи что делает эта прога??? blink.gif
при n=5 и s='12345' ответ=119 mega_chok.gif ...
почему это так? wacko.gif

Добавлено через 6 мин.
помоему я нашел... надо просто стереть функцию Fact и написать writeln(p); вместо writeln(total-p);...
вот и все... огромное спасибо за помощь Volvo
volvo
Ну, да... Там же немного другая задача стояла... Тебе достаточно WriteLn(p) ...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.