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

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

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

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

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

136598247

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

Давайте получим размещение P_i+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.

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