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

Генерация размещения с повторениями по номеру

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

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

Как и ранее алфавитом будем считать первые k цифр начиная с нуля. Длина размещения равна n. Необходимо по номеру сгенерировать размещение с повторениями в лексикографическом порядке.
Для начала давайте рассмотрим все размещения с повторениями для n = 2 и k = 4:

  1. 00
  2. 01
  3. 02
  4. 03
  5. 10
  6. 11
  7. 12
  8. 13
  9. 20
  10. 21
  11. 22
  12. 23
  13. 30
  14. 31
  15. 32
  16. 33

Внимательный читатель возможно уже нашел закономерность между порядковым номером и размещением. Если внимательно присмотреться, то можно заметить, что размещения с повторениями это числа в k-ричной системе счисления и их перечисление в лексикографическом порядке полностью совпадает с их перечислением в порядке возрастания.
Проверим наше утверждение на размещении “31”: 314=4*3+1=13. Но размещение “31” соответствует 14 размещению. Номер 13 получился, потому что нумерация размещений изначально начинается с 0.
Данная логика отображена в следующей функции:

  1. typedef unsigned long long ULL;
  2. void gen_placement_rep_by_num(vector<int> &cur, ULL num, int n, int k) {
  3.   cur.assign(n,0);
  4.   int pos = n - 1;
  5.   while (num) {
  6.     cur[pos--] = num % k;
  7.     num /= k;
  8.   }
  9. }
* This source code was highlighted with Source Code Highlighter.

Если значения n и k настолько велики, что не помещаются в unsigned long long необходимо использовать длинную арифметику.

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

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