Занятие 3

Получение k-ой перестановки

Найти k-ую в лексикографическом порядке перестановку

int n;
int b[100]; // массив с числами 1,..., n
void rec(int i, int k)
{ int j, t, f;
  if(i==n)
  { for(i=0; i<n; ++i)
      printf("%d%c",b[i],i<n-1?' ':'\n');
    return;
  }
  // считаем (n-i-2)!
  f=1;
  for(j=i+1; j<n; ++j)
    f*=j-i;
  // подстановка на i-ое место всех элементов с i по n-1
  for(j=i; j<n; ++j)
  { 
    t=b[i];
    b[i]=b[j];
    b[j]=t;
    if(k<=f)
      rec(i+1);
    else
      k-=f;
  }
}
// вызов rec(0,k);

Обратная задача решается также просто

int n;
int b[100]; // массив с числами 1,..., n
int a[100]; // массив с нужной перестановкой
void rec(int i, int k)
{ int j, t, f;
  if(i==n)
  { printf("%d\n",k);
    return;
  }
  // считаем (n-i-2)!
  f=1;
  for(j=i+1; j<n; ++j)
    f*=j-i;
  // подстановка на i-ое место всех элементов с i по n-1
  for(j=i; j<n; ++j)
  { 
    t=b[i];
    b[i]=b[j];
    b[j]=t;
    if(b[i]==a[i])
      rec(i+1,k);
    else
      k+=f;
  }
}
// вызов rec(0,1);