H. Weird Permutations @ Romanian Open Contest December 2001 @ Timus Online Judge

H. Weird Permutations

Time limit: 0.5 second
Memory limit: 64 MB

Three Romanian programmers developed this new algorithm which generates all the N! permutations with N elements in a specific order, they called the transposition order. The algorithm starts with the permutation 1 2 3 .. N. Then it chooses a pair of two adjacent elements (that is, two elements which are located on consecutive positions) and switches them. This way, they get a new permutation. They do the same for this new permutation and they obtain a new one and so on, until all the N! permutations are generated. You realize that the algorithm must be pretty smart in order to generate all the N! permutations exactly once (without repetitions).

Hopefully, your task will not be to write such an algorithm. In fact, you are given the files perm.pas and perm.cpp, which are two implementations of this algorithm (in Pascal and C++). They read the integer N (1 ≤ N ≤ 100) from the keyboard and print to the file perm.txt all the N! permutations, one per line, in the order in which the algorithm generates them.

What you have to do is, given a permutation, to find out its index in the list of permutations generated by the algorithm.

Perm.pas

Perm.cpp

const
  fileout = 'perm.txt';
  MAXN = 100;

var
  fout :text;
  n, i :integer;
  permut :array [1..MAXN] of integer;
  position :array [1..MAXN] of integer;
  dir :array [1..MAXN] of integer;

procedure PrintPermutation;
begin
  for i := 1 to n do
    write(fout, ' ', permut[i]);
  writeln(fout);
end;

procedure Switch(p1, p2 :integer);
var
  xch :integer;
begin
  xch := permut[p1];
  permut[p1] := permut[p2];
  permut[p2] := xch;
  position[permut[p1]] := p1;
  position[permut[p2]] := p2;
end;

procedure GeneratePermutation(nn :integer);
var ii :integer;
begin
  if (nn = n + 1) then
    PrintPermutation
  else
  begin
    GeneratePermutation(nn + 1);
    for ii := 1 to nn - 1 do
    begin
      Switch(position[nn],
             position[nn] + dir[nn]);
      GeneratePermutation(nn + 1);
    end;
    dir[nn] := -dir[nn];
  end;
end;

begin
  readln(n);
  for i := 1 to n do
  begin
    permut[i] := i;
    position[i] := i;
    dir[i] := -1;
  end;

  assign(fout, fileout);
  rewrite(fout);

  GeneratePermutation(1);

  close(fout);
end.

#include <stdio.h>

const char *fileout = "perm.txt";
const int MAXN = 100;

FILE *fout;
int n, i;
int permut[MAXN + 1];
int position[MAXN + 1];
int dir[MAXN + 1];

void PrintPermutation()
{
  for (i = 1; i <= n; i++)
    fprintf(fout, " %d", permut[i]);
  fprintf(fout, "\n");
}

void Switch(int p1, int p2)
{
  int xch = permut[p1];
  permut[p1] = permut[p2];
  permut[p2] = xch;
  position[permut[p1]] = p1;
  position[permut[p2]] = p2;
}

void GeneratePermutation(int nn)
{
  int ii;

  if (nn == n + 1)
    PrintPermutation();
  else
  {
    GeneratePermutation(nn + 1);
    for (ii = 1; ii <= nn - 1; ii++)
    {
      Switch(position[nn],
             position[nn] + dir[nn]);
      GeneratePermutation(nn + 1);
    }
    dir[nn] = -dir[nn];
  }
}

int main()
{
  scanf("%d", &n);
  for (i = 1; i <= n; i++)
  {
    permut[i] = i;
    position[i] = i;
    dir[i] = -1;
  }

  fout = fopen(fileout, "wt");

  GeneratePermutation(1);

  fclose(fout);
  return 0;
}

Input

The first line contains a single integer: N (1 ≤ N ≤ 100). The 2nd line contains N integers separated by blanks. They are the given permutation with N elements.

Output

Print one single integer, which will be the index of the permutation in the list of N! permutations generated by the algorithm described above.

Sample

input	output
4 2 3 1 4	17

Notes

Run the 2 given programs for N=4 and you will notice that the permutation 2 3 1 4 will be on the 17th line of the file perm.txt.

Problem Author: Mugurel Ionut Andreica. The Pascal and C++ programs of the three programmers are improved (and, obviously, modified) versions of two programs written by Frank Ruskey (I found them on the Web). So, thanks Frank!
Problem Source: Romanian Open Contest, December 2001