Генерация размещения без повторений по номеру за 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.