пятница, 16 марта 2012 г.

Генерация размещения без повторений по номеру за O(N*N)

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: [3784. Генерация размещений]

Ранее мы рассмотрели получение номера по размещению за O(N*N). В данной же задаче нужно сделать все с точностью до наоборот:

  1. int placement_amount(int n, int m) {
  2.   int res = 1;
  3.   for (int i = n; i >= n-m+1; --i) {
  4.     res *= i;
  5.   }
  6.   return res;
  7. }
  8. void gen_placement_by_num(int num, int n, int m, vector<int> &mas) {
  9.   vector<bool> usd(n,false);
  10.   int _n = n-1, _m = m-1;
  11.   for (int i=0;i<m;++i) {
  12.     int block_cnt = num / placement_amount(_n,_m);
  13.     num -= block_cnt * placement_amount(_n,_m);
  14.     int pos = 0;
  15.     ++block_cnt;
  16.     while (block_cnt) {
  17.       if (!usd[pos])
  18.         --block_cnt;
  19.       ++pos;
  20.     }
  21.     usd[pos-1] = true;
  22.     mas[i] = pos;
  23.     --_n; --_m;
  24.   }
  25. }
* This source code was highlighted with Source Code Highlighter.

При многократном вызове функции gen_placement_by_num можно сделать препроцессинг и не использовать функцию placement_amount.

Комментариев нет:

Отправить комментарий