Буквометика. Метод ветвей и границ.

Данный пост навеян главой “2.8.3. Расшифровка криптограм” из книги В.Д. Колдаева “Основы алгоритмизации и программирования”.

Напомним, что о теме Буквометики говорилось ранее.
Вкратце напомню, что суть задачи в решении ребуса, подобному этому:
                           MOTOR 
                     +      FIAT  
                          ------
                           VOLVO
где вместо букв нужно подставить цифры, при этом две различные буквы должны иметь различный цифровой эквивалент.

Описание:
В предыдущем посте перебирались все размещения без повторений, после чего проверялась корректность получившегося набора.

Суть же рассматриваемого подхода заключается в том, что перебираться будут не все комбинации, а только те, которые удовлетворяют набору логических правил. О правилах речь пойдет ниже. Если набор цифровых эквивалентов удовлетворяет полному набору правил, то ребус корректен.

Рассмотрим текущий ребус.
Представим ребус в виде матрицы из трех строк, и столбцов, количество которых равно длине суммы. В первой строке хранится первое слагаемое, во второй – второе, в третье – сумма. Если имеется ведущий ноль(как например в FIAT), то храним ведущий пробел на первом месте.
Учитывая все вышесказанное, получаем матрицу
                             01234
                         0 [ MOTOR ]
                         1 [ _FIAT ]
                         2 [ VOLVO ]
символ ‘_’ соответствует пробелу.

Будем формировать правила при проходе по матрице сверху вниз, слева направо.
1) На букву M накладывается только одно ограничение – оно не может быть равным 0, и следовательно может принимать любое значение из интервала. [1,9]
2) Буква V однозначно получается из значения M и переноса, соответствующего 0-ому столбцу, который определяется из суммы O+F.
Следовательно если перенос(p[0]) равен нулю, тогда
2.1) V = M и O + F < 10
Если p[0] = 1, тогда
2.2) V = M + 1 и O + F >=10.

Здесь необходимо учесть тот факт, что на сумму O + F будет еще влиять перенос на первом столбце, поэтому правильно будет так:
2.1) V = M     и O + F + p[1] < 10
2.2) V = M + 1 и O + F + p[1] >=10.
3) Буква O может принимать любые значения из интервала [0,9]
4) Буква F будет вычисляться из неравенства 2.1) или 2.2) в зависимости от значения переноса p[0] и равенства O+F=O
И т.д. до конца. Если на каком то этапе получается, что текущая буква не может иметь ни одного значения, значить необходимо поменять значения ранее стоящих букв, или значения переносов.

Реализация:
Удобно решать рекурсивно. При этом сама рекурсия будет иметь прототип: void rec(int row, int col, int prevCarry, int carry), где row и col – номера строки и столбца текущего элемента в матрице, а prevCarry и carry – значения переноса на предыдущем и  текущем разрядах.

Правила, образующие неравенства удобно хранить в виде структуры:

1. struct rule {
2. // this + pair < 10, если prevCarry == 0
3. // this + pair >=10, если prevCarry == 1
4.   char pair;     // парный символ   
5.   int prevCarry; // предыдущий перенос
6.   int carry;     // текущий перенос
7. };

* This source code was highlighted with Source Code Highlighter.

А набор правил в виде рванной матрицы:
vector<vector<rule> > rules(256);
где значение буквы this определяется номер строки в рванной матрице правил.
Например рассмотрим правило, где фигирируют буквы A,O. prevCarry = 1, carry = 1.
Из представленных значений ясно, что A + O + carry >= 10. Правило занесем таким способом: 
rules[‘A’].push_back(rule(‘0’,prevCarry,carry));

[Решение]

P.S: К сожалению не удалось зачесть эту реализацию на задаче 251.Футбол и математика из-за Memory Limit. Но от этого данный подход не теряет своей привлекательности по быстродействию.

Часть 5. Буквометика

[Все темы по перестановкам]

Литература: Кнут. Том 4. Выпуск 2. Генерация всех картежей и перестановок. 2008

Задача: Футбол и математика

Описание решение:
Суть задачи решить ребус аналогичный такому:
                        MOTOR
                  +      FIAT 
                       ------
                        VOLVO
Где вместо букв нужно поставить цифру. При этом разные буквы должны иметь разные цифровые значения.
По условию задачи количество различных букв не превосходит 10.
Значит в общем случае нужно перебрать все размещения без повторений для n=10(10 цифр) и k = количеству различных букв в ребусе. А в худшем случае – 10! различных перестановок.
Генерация размещений без повторений имеет схожую природу с генерацией перестановок без повторений. Поэтому данная задача попала в блок к перестановкам.

Алгоритм будет иметь следующую структуру:
1) Получение строки, содержащей все различные буквы исходного ребуса в порядке слева направо, сверху вниз. Для примера это будет строка “MOTRFIAVL”.
1) Генерация текущего размещения без повторений для заданных n и k в лексикографическом порядке.
2) Т.к. длина текущего размещения равна длине строке различных букв из п.1), проинициализировать i-ую букву i-ым значением размещения.
3) Проверка корректности ребуса.
4) Если возможно, перейти на п. 1).

Реализация:
В самом решении использовалась рекурсивная схема, схожая со схемой генерации всех перестановок без повторений.
Обратите внимание на изящную реализацию считывания(ст.4):

1. void input()
2. {
3.   char a[12],b[12],c[12];
4.   scanf("%[A-Z]+%[A-Z]=%[A-Z]",&a,&b,&c);
5.   A = string(a); B = string(b); C = string(c);
6. }

* This source code was highlighted with Source Code Highlighter.

[Решение]

P.S: Метод ветвей и границ для данной задачи.

Часть 4. Генерация перестановки по номеру и получение номера по перестановке

[Все темы по перестановкам]

Теория: Окулов. Программирование в алгоритмах. 2004.

Рассмотрим две задачи:
1) Генерация перестановки по номеру
2) Получение номера по перестановке

Генерация перестановок происходит в лексикографическом порядке. Нумерация перестановок начинается с единицы.

Практика: 
Обе задачи реализуем на основе problem Перестановка по номеру.

1) Генерация перестановки по номеру
Вся необходимая теория довольно популярно изложена в книге Окулова. Остановлюсь на некоторых моментах. Перестановку будем последовательно получать слева направо. Сначала мы имеем N пустых позиций перестановки. Если выписать в столбец все перестановки в лексикографическом порядке то увидим, что их можно разбить на N групп размерностью по (N-1)! каждая. Зная номер перестановки можно без проблем определить в какую группу она попадет. Номер группы и уже полученное начало перестановки однозначно определяют текущий элемент перестановки.
Общую логику передает функция permutation_by_num:

1. int fact[13] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,  39916800, 479001600};
2. int notUsed(vector<bool> &used, int blockNum) {
3.  
4.   int j, pos = 0;
5.   for (j = 1; j < used.size(); j++) {
6.     if (!used[j]) pos++;
7.     if (blockNum == pos)
8.       break;
9.   }
10.   return j;
11. }
12. vector<int> permutation_by_num(int n, int num) {
13.  
14.   vector<int> res(n); 
15.   vector<bool> used(n+1,false);
16.  
17.   for (int i = 0; i < n; i++) {
18.     int blockNum = (num - 1) / fact[n - i - 1] + 1;
19.     int j = notUsed(used, blockNum);
20.     res[i] = j;
21.     used[j] = true;
22.     num = (num - 1) % fact[n - i - 1] + 1;
23.   }
24.   return res;
25. }

* This source code was highlighted with Source Code Highlighter.

[Решение]

2) Получение номера по перестановке
Для решения этой задачи в первую очередь нужно понять принцип решения первой задачи, а потом проделать обратные манипуляции.
Мне не удалось найти problem, которая в чистом виде решает поставленную задачу. Но у нас есть problem Перестановка по номеру, на основе которой можно проверить правильность решения этой задачи.

[Решение]

Часть 3. Генерация перестановок с повторениями

[Все темы по перестановкам]

Теория:
1. Меньшиков. Олимпиадные задачи по программированию. 2006
2. Окулов. Дискретная математика. Теория и практика решения задач по информатике. 2008
3. Кнут. Том 4. Выпуск 2. Генерация всех кортежей и перестановок. 2008

Рассмотрим три задачи:
1) Рекурсивный способ генерации всех перестановок с повторениями в лексикографическом порядке
2) Генерация следующей перестановки с повторениями в лексикографическом порядке(next_permutation)
3) Генерация предыдущей перестановки с повторениями в лексикографическом порядке(prev_permutation)

Практика:
Все задачи будем решать на основе 3B-Перестановки(2)

Аналогичные алгоритмы, реализованные ранее относительно перестановок без повторений неприемлемы для перестановок с повторениями.  Обратное неверно. Поэтому реализация для предложенных выше задач будет универсальной и будет работать для перестановок без повторений.

1) Рекурсивный способ генерации всех перестановок с повторениями в лексикографическом порядке.
Суть реализации взята из авторского разбора задачи 3B.
[Решение]
2) Генерация следующей перестановки с повторениями в лексикографическом порядке(next_permutation)

1. bool next_permutation(string &a) {
2.  
3.   int j = n-2;
4.   while (j!=-1 && a[j] >= a[j+1]) j--;
5.   if (j == -1)
6.     return false; // a - last permutation
7.   int k = n - 1;
8.   while (a[j] >= a[k]) k--;
9.  
10.   swap(a[j],a[k]);
11.  
12.   // reverse back [j+1, n-1]
13.   int l = j + 1, r = n - 1;
14.   while (l<r)
15.     swap(a[l++],a[r--]);
16.   return true;
17. }

* This source code was highlighted with Source Code Highlighter.

Данная реализация очень напоминает аналогичную функцию относительно перестановок без повторения. Если хорошенько присмотреться, то строгое сравнение в строках 4 и 8 теперь стало нестрогим.
[Решение]
3) Генерация предыдущей перестановки с повторениями в лексикографическом порядке(prev_permutation)

1. bool prev_permutation(string &a) {
2.  
3.   int j = n-2;
4.   while (j != -1 && a[j] <= a[j+1]) j--;
5.   if (j == -1) return false;
6.   int k = n - 1;
7.   while (a[j] <= a[k]) k--;
8.  
9.   swap(a[j], a[k]);
10.  
11.   int l = j+1, r = n-1;
12.   while (l<r)
13.     swap(a[l++],a[r--]);
14.   return true;
15. }

* This source code was highlighted with Source Code Highlighter.

Здесь нужно грамотно обратить все действия, которые использовались при генерации следующей перестановки.
[Решение]

Часть 2. Генерация перестановок без повторений. Episode 2

[Все темы по перестановкам]

Теория:
1. Окулов. Программирование в алгоритмах. 2004.
2. Липский. Комбинаторика для программистов. 1988
3. Кнут. Том 4. Выпуск 2. Генерация всех кортежей и перестановок. 2008

Рассмотрим две задачи:
1) Генерация следующей перестановки в лексикографическом порядке
2) Генерация всех перестановок с помощью транспозиции двух соседних элементов.

В книге Липского описан алгоритм, генерирующий все перестановки с помощью транспозиций двух элементов(не обязательно соседних).

Практика:
Как и в первой части будем решать задачу 2B-Перестановки

1) Генерация следующей перестановки в лексикографическом порядке(next_permutation).
Данный подход очень хорошо описан в книге Окулова, а также его подробное описание можно найти в книге Кнута(алгоритм L).

1. bool next_permutation(string &a) {
2.  
3.   int j = n-2;
4.   while (j!=-1 && a[j] > a[j+1]) j--;
5.   if (j == -1)
6.     return false; // a - last permutation
7.   int k = n - 1;
8.   while (a[j] > a[k]) k--;
9.  
10.   swap(a[j],a[k]);
11.  
12.   // reverse back [j+1, n-1]
13.   int l = j + 1, r = n - 1;
14.   while (l<r)
15.     swap(a[l++],a[r--]);
16.   return true;
17. }

* This source code was highlighted with Source Code Highlighter.

Отметим тот факт, что изначально перестановка a должна быть минимальной, т.е. необходимо отсортировать элементы перестановки в порядке возрастания.
[Решение]

2)Генерация всех перестановок с помощью транспозиции двух соседних элементов
Опять же направляю в книгу Окулова, в котором имеется превосходное описание данного алгоритма на основе таблицы инверсий:

[Решение]