четверг, 22 марта 2012 г.

Генерация следующего и предыдущего размещения с повторениями

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

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

Пусть задан алфавит, состоящих из первых k цифр, начиная с 0. Также имеется текущее размещение с повторениями длины n. Найдем следующее размещение с повторениями в лексикографическом порядке.

Ri = {1, 5, 6, 4, 6}; n = 5; k = 7
Ri+1 = {1, 5, 6, 5, 0}

Для генерации следующего размещения будем пользоваться простым правилом:
Перебираем все элементы справа налево. Если текущий элемент равен k-1, тогда обнуляем его и переходим к элементу левее. В противном случае увеличиваем текущий элемент на 1 и заканчиваем генерацию. Если на текущем шаге были перебраны все элемента размещения, но не получилось инкрементировать никакой элемент, значит на текущем шаге мы работали с последним размещением для заданных n и k.

  1. bool next_placement_rep(vector<int> &cur, int n, int k) {
  2.   int r = 1;
  3.   int pos = n-1;
  4.   while (pos>=0 && r) {
  5.     cur[pos]++;
  6.     r = cur[pos] == k;
  7.     if (r) cur[pos] = 0;
  8.     --pos;
  9.   }
  10.   return !r;
  11. }
* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация предыдущего размещения делается по аналогичной схеме:

  1. bool prev_placement_rep(vector<int> &cur, int n, int k) {
  2.   int r = 1;
  3.   int pos = n-1;
  4.   while (pos >=0 && r) {
  5.     cur[pos]--;
  6.     r = cur[pos] == -1;
  7.     if (r) cur[pos] = k-1;
  8.     --pos;
  9.   }
  10.   return !r;
  11. }
* This source code was highlighted with Source Code Highlighter.

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

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