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

Получение номера по размещению с повторениями

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

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Ранее мы научились генерировать размещение с повторениями по номеру. Как выяснилось вся задача свелась к переводу числа из 10-ой в k-ричную систему счисления. Текущая задача представляет собой обратное действие, следовательно будем переводить “число” из k-ричной в 10-ую систему.

Пусть размещение R = {2, 0, 2, 2, 1, 1, 1, 2}; n = 8; k = 3. Найдем номер этого размещения в лексикографическом порядке.
202211123=2*2187+0*729+2*243+2*81+1*27+1*9+1*3+2*1=4374+486+162+27+9+3+2=506310.

Учитывая, что нумерация всех размещений начинается с 0, получаем что размещение R имеет порядковый номер 5064.

  1. typedef unsigned long long ULL;
  2. ULL get_num_by_placement_rep(const vector<int> &cur, int n, int k) {
  3.   ULL num = 0;
  4.   ULL step = 1;
  5.   for (int i=cur.size()-1;i>=0;--i) {
  6.     num += cur[i] * step;
  7.     step *= k;
  8.   }
  9.   return num;
  10. }
* This source code was highlighted with Source Code Highlighter.

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

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