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

Получение номера по размещению без повторений за 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.

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

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