Получение номера по размещению без повторений за O(N*N)

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

Теория: Окулов. Программирование в алгоритмах. 2004.
Практика: 192. По размещению!

Рассмотрим все размещения для n = 4 и m = 3:

1. 123
2. 124
3. 132
4. 134
5. 142
6. 143
7. 213
8. 214
9. 231
10. 234
11. 241
12. 243
13. 312
14. 314
15. 321
16. 324
17. 341
18. 342
19. 412
20. 413
21. 421
22. 423
23. 431
24. 432

* This source code was highlighted with Source Code Highlighter.

Можно заметить, что все размещения можно разбить на 4(n) блока. Элементы первого блока начинаются на 1, второго - на 2 и т.д. В каждом блоке находится равное количество элементов равное (n-1)!/(n-m)!. В нашем случае по 6 элементов.
Зная значения n и m и текущее размещение, можно найти размер блока B и определить интервал [L,R], в котором лежат все размещения, начинающиеся на общий первый элемент.
L = B * LESS, где LESS - количество элементов алфавита, меньших первого элемента размещения.
R = L + B – 1.
Далее извлекаем первый элемент размещения из общего алфавита и решает ту же задачу для n`=n-1 и m`=m-1. Рассмотрим идею на конкретном примере:
Пусть n = 9, m = 7. Размещение R = {6, 3, 8, 1, 9, 4, 7}.

Итерация	Размещение	Размер блока	Нижняя граница	Неиспользованный члены
1	6******	8!/2! = 20160	5*20160 = 100800	123456789
2	63*****	7!/2! = 2520	2*2520  =   5040	12345789
3	638****	6!/2! = 360	5*360   =   1800	1245789
4	6381***	5!/2! = 60	0*60    =      0	124579
5	63819**	4!/2! = 12	4*12    =     48	24579
6	638194*	3!/2! = 3	1*3     =      3	2457
7	6381947	2!/2! = 1	2*1     =      2	257

Номер размещения будет равен сумме нижних границ интервалов на каждой итерации:
100800+5040+1800+0+48+3+2 = 107693. Полученный номер был получен с тем расчетом, что изначально все размещения нумеровались с нуля.
Все вышесказанное можно реализовать таким образом:

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. int get_num_by_placement(const vector<int> &mas, int n, int m) {
9.   vector<bool> usd(n,false);
10.   int res = 0;
11.   int _n = n-1, _m = m-1;
12.   for (int i=0;i<mas.size();++i) {
13.     int amount = 0;
14.     for (int j=0;j<n;++j) {
15.       if (!usd[j]) amount++;
16.       if (mas[i] == j) {
17.         int ampt = (amount - 1) * placement_amount(_n, _m);
18.         res += (amount - 1) * placement_amount(_n, _m);
19.         usd[j] = true;
20.       }
21.     }
22.     usd[mas[i]] = true;
23.     --_n; --_m;
24.   }
25.   return res;
26. }

* This source code was highlighted with Source Code Highlighter.