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

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

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

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

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

Учитывая, что нумерация всех размещений начинается с 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.