среда, 14 марта 2012 г.

Генерация следующего размещения без повторений за O(N*N) и O(N*log(N))

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

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: K4.Размещения.(dl.gsu.by)

Пусть n = 9, а m = 6. Рассмотрим текущее размещение Pi = {1,3,6,5,9,8}. Найдем следующее размещение Pi+1 в лексикографическом порядке. Алфавитом в данном случае будет являться набор цифр от 1 до 9.

Для начала разделим все элементы алфавита на две группы: те, что входят в текущее размещение Pi и те, что нет(множество F - свободные члены):
 

136598247

Будем последовательно перебирать элементы размещения Pi справа налево. Если на каком-то этапе для текущего элемента размещения Pi[j] можно найти элемент F[k] из свободных членов, который больше его, то заменяем Pi[j] на F[k]. При этом F[k] должен быть минимально возможным. При этом может возникнуть две ситуации:
1) Это сделать удалось. При это нужно дополнить размещение так, чтобы ее размер стал равным m. Для этого на свободные места последовательно добавляем элементы множества F в порядке возрастания начиная с самого маленького.
2) Этого сделать не удалось. Текущий элемент Pi[j] удаляем из текущего размещения и добавляем в множество F. Берем следующий элемент Pi[j-1] и повторяем итерацию. Если же не удалось найти такой элемент, значит на текущей итерации мы работали с последним размещением в лексикографическом порядке.

Давайте получим размещение Pi+1 по вышеизложенным правилам:

Pi   = 136598247

Нет свободного элемента больше 8

136592478

Нет свободного элемента больше 9

136524789

Есть 3 свободных элемента больше 5: 7,8,9. Выбираем 7 и меняем их местами

136724589

Первые 4 элемент размещения Pi+1 определены

Pi+1 = 136724589 Дополняем префикс размещения Pi+1

Данный подход можно реализовать со сложностью O(N*N):

  1. string letters = "1234567";
  2. bool next_placement(string &cur, vector<bool> &usd, int n, int m) {
  3.   int beg = -1;
  4.   for (int i=m-1;i>=0;--i) {
  5.     if (beg != -1) break;
  6.     for (int j=cur[i] - letters[0] + 1; j < n; ++j) {
  7.       if (!usd[j]) {
  8.         usd[j] = true;
  9.         usd[cur[i] - letters[0]] = false;
  10.         cur[i] = letters[j];
  11.         beg = i;
  12.         break;
  13.       }
  14.     }
  15.     if (beg == -1)
  16.       usd[cur[i] - letters[0]] = false;
  17.   }
  18.   if (beg != -1) {
  19.     for (int i=beg+1, j = 0; i<m && j<n;++j) {
  20.       if (!usd[j]) {
  21.         usd[j] = true;
  22.         cur[i++] = letters[j];
  23.       }
  24.     }
  25.     return true;
  26.   }
  27.   else
  28.     return false;
  29. }
* This source code was highlighted with Source Code Highlighter.

Рассмотрим параметры, передаваемые в функцию next_placement:
1. cur – текущее размещение.
2. usd – массив меток. Если usd[i] == false, значит i-ый элемент алфавита является свободным членом.
Т.к. текущее размещение cur передается по ссылке, то после выполнения функции оно заменится на следующее размещение в лексикографическом порядке.

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

Немного подумав, можно смело заменить массив меток на множество(set) свободных членов, улучшив асимптотику до O(N*log(N)):

  1. bool next_placement(string &cur, set<char> &vac, int n, int m) {
  2.   set<char>::iterator it;
  3.   for (int i=cur.size()-1;i>=0;--i) {
  4.     it = vac.lower_bound(cur[i]);
  5.     if (it != vac.end()) {
  6.       char tmp = cur[i];
  7.       cur[i] = *it;
  8.       vac.erase(it);
  9.       vac.insert(tmp);
  10.       for (int pos = i+1; pos < m; ++pos) {
  11.         cur[pos] = *vac.begin();
  12.         vac.erase(vac.begin());
  13.       }
  14.       return true;
  15.     }
  16.     vac.insert(cur[i]);
  17.   }
  18.   return false;
  19. }
* This source code was highlighted with Source Code Highlighter.

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

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

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