понедельник, 28 февраля 2011 г.

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

Данный пост навеян главой “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. Но от этого данный подход не теряет своей привлекательности по быстродействию.

вторник, 15 февраля 2011 г.

Часть 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: Метод ветвей и границ для данной задачи.

пятница, 11 февраля 2011 г.

Часть 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 Перестановка по номеру, на основе которой можно проверить правильность решения этой задачи.

[Решение]

вторник, 8 февраля 2011 г.

Часть 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)Генерация всех перестановок с помощью транспозиции двух соседних элементов
Опять же направляю в книгу Окулова, в котором имеется превосходное описание данного алгоритма на основе таблицы инверсий:

[Решение]

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

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

Теория:
1) Липский. Комбинаторика для программистов. 1988
2) Меньшиков. Олимпиадные задачи по программированию. 2006.

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

Для начала разберемся, что такое лексико- и антилексико-графические порядки.
Начальная перестановка: {1, 2, 3}

Лексикографический

Антилексикографический

0 1 2 3 1 2 3
1 1 3 2 2 1 3
2 2 1 3 1 3 2
3 2 3 1 3 1 2
4 3 1 2 2 3 1
5 3 2 1 3 2 1

Напомним, что лексикографический порядок – это порядок слов, который используется в словарях.
Слово A меньше слова B, если первые i символов слов равны, а символ A[i+1] < B[i+1]. Отсюда вытекает следствие, что если слово А является началом слова B, то A < B.

Антилексикографический порядок отличается от лексикографического только тем, что сравнение символов идет справа налево.
Слово A меньше слова B, если последние i символов равны, а символ A[i-1] < B[i-1]. Также следует, что если слово B заканчивается на слово A, то A < B.

Практика:
Решим задачу
2B-Перестановки из задачника Федора Меньшикова двумя рассматриваемыми способами.
Как можно было заметить, оба порядка начинаются с минимальной перестановки {1, 2, 3} и заканчивается максимальной {3, 2, 1}.

1) Генерация всех перестановок в лексикографическом порядке.
  1. int n;
  2. vector<int> p;
  3. vector<bool> used;
  4. string str;
  5. ...
  6. void lex(int pos)
  7. {
  8.   if (pos == n) {
  9.     for (int i=0;i<n;i++)
  10.       cout<<str[p[i]];
  11.     cout<<endl;
  12.     return;
  13.   }
  14.   for (int i=0;i<n;i++) {
  15.     if (!used[i]) {
  16.       used[i] = true;
  17.       p[pos] = i;
  18.  
  19.       lex(pos+1);
  20.      
  21.       p[pos] = 0; // debug only
  22.       used[i] = false;
  23.     }
  24.   }
  25. }
* This source code was highlighted with Source Code Highlighter.

Рекурсивная функция lex(n) генерируется все перестановки из алфавита {0,1,..n-1} длиной n и хранит текущую перестановку в массиве p. Если номер текущей позиции pos == n, тогда сгенерирована следующая перестановка.
[Решение]

2) Генерация всех перестановок в антилексикографическом порядке
Решение полностью идентично, за исключением того, что перестановка формируется с конца
[Решение]

понедельник, 7 февраля 2011 г.

Часть 1. Знак перестановки. Подсчет количества инверсий

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

Теория: Липский. Комбинаторика для программистов. 1988
Особое внимание нужно уделить понятиям инверсии перестановки и знаку перестановки.

sgn(f) = pow(-1,I(f)),
где sgn(f) – знак перестановки, I(f) – количество инверсий

В Липском описан алгоритм, который линейно определяет четность перестановки: четность перестановки равна четности количества четных циклов перестановки.
Мы же сегодня будем заниматься определением количества инверсий в перестановках.

Практика:
В качестве базовой задачи рассмотрим
1090.In the Army Now и решим ее тремя способами.

1 Способ: Сортировка слиянием (merge_sort)   O(NlogN)
Суть метода можно легко понять на основе перестановки:

{4, 5, 6, 1, 2, 3}

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

[Решение] 

В следующих двух способах придерживаемся общего правила:

Последовательно проходим по каждому элементу перестановки и отвечаем на вопрос: “Сколько элементов было до текущего, которые больше него?”.
2 Способ: Карманная сортировка (bucket_sort) O(N)
Для ответа на вопрос при карманной сортировке нужно определить карман B, в который попадет текущий элемент. Затем найти количество элементов в старших карманах относительно B. Потом аккуратно подсчитать количество элементов, больших текущего в кармане B.
Карман A считается старшим для кармана B, если любой элемент из A больше любого элемента из B.

[Решение]

3 Способ: Дерево Фенвика (Fenwick_tree)      O(NlogN)
Сложилось впечатление, что там, где пытаются пристроить карманную сортировку не по назначению, всегда есть место для Дерева Фенвика. И как показывает практика использование дерева Фенвика дает хороший выигрыш по времени, несмотря на свою алгоритмическую сложность.
Вспоминаются слова Михаила Мирзаянова: “Хорошо написанный куб может работать быстрее плохо написанного квадрата”.
По решению: Чтобы найти количество элементов, больше текущего, которые были раньше, необходимо уметь находить быстро сумму элементов в интервале от [cur+1,MAX_VALUE], где cur – текущий элемент, а MAX_VALUE – максимальный элемент в перестановке.
[Решение]

пятница, 4 февраля 2011 г.

Часть 0. Понятие перестановки. Разложение на циклы.

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

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


Практика:

Задача:
[Обратная перестановка]
Сама задача несложная. Нужно понять принцип суперпозиции двух перестановок, откуда вытекает понятие обратной перестановки. Все справочные материалы можно найти в Липском.
[Решение]

Задача:[Степень перестановки]
Рассмотрим перестановку: (5 7 8 2 3 1 4 6)
Как известно любую перестановку можно разложить ни циклы. Данная перестановка выглядит вот так:

Теперь давайте рассмотрим маленький цикл [274].
Как видно для того, чтобы номера вершин “встали на свои позиции” нужно получить третью степень исходной перестановки.

Проделаем тоже самое для большого цикла [15386]. Здесь нам придется получить пятую степень перестановки.
Вопрос: Когда все 7 позиций “встанут” на свои места. Очевидно, когда первый цикл сделает 5 оборотов, а второй – 3. Следовательно нужно получить 15-ую степень исходной перестановки.

В общем случае нужно найти НОК(lcm) длин всех циклов, которые присутствуют в перестановке.
[Решение]

Задача: [Восстановление перестановки]
Интересный факт: в разной литературе дают разное определение таблице инверсий перестановки.
В задаче: Phi[i]    = amount(j): П(j) > П[i], j<i
Окулов:   Phi[П[i]] = amount(j): П[j] < П[i], j>i
Кнут:    
Phi[П[i]] = amount(j): П[j] < П[i], j<i

Сути дела это правда не меняет. Главное быть в курсе по какому правилу получается эта таблица инверсий.

Что касается задачи. Будем последовательно находить положение элементов в перестановке на основе данной таблице инверсий. При этом заполнять перестановку будем элементами в порядке возрастания. Более подробно об этом процессе читайте у Окулова.
[Решение]

Перестановки (permutations)

Количество перестановок без повторений: N!
Количество перестановок с повторениями: N!/(k1!*k2!*..*kn!),
где N-общее количество элементов, ki – количество вхождений i-ого элемента

0. Понятие перестановки. Разложение на циклы + [Video]   
    Практика: [Обратная перестановка]
             
[Степень перестановки]
             
[Восстановление перестановки]

1. Знак перестановки. Подсчет количества инверсий.
    Практика:[In the Army Now(timus 1090)] merge sort + [Video]
            
[In the Army Now(timus 1090)] bucket search + [Video]
            
[In the Army Now(timus 1090)] fenwic tree + [Video]

2. Генерация перестановок без повторений(Episode 1, Episode2).

Episode 1
    2.1. Рекурсивный способ генерации всех перестановок в лексикографическом порядке.
        Практика:
[Меньшиков 2B]
    2.2. Рекурсивный способ генерации всех перестановок в антилексикографическом порядке.
        Практика:
[Меньшиков 2B]

Episode 2
    2.3. Генерация следующей перестановки в лексикографическом порядке.
        Практика:
[Меньшиков 2B]
    2.4. Генерация всех перестановок с помощью транспозиции двух соседних элементов.
        Практика:
[Меньшиков 2B]

3. Генерация перестановок с повторениями.
    3.1. Рекурсивный способ генерации всех перестановок в лексикографическом порядке.
        Практика:
[Меньшиков 3B]
    3.2. Генерация следующей перестановки в лексикографическом порядке.
        Практика:
[Меньшиков 3B]
    3.3. Генерация предыдущей перестановки в лексикографическом порядке.
        Практика:
[Меньшиков 3B]

4. Генерация перестановки по номеру и получение номера по перестановке.
    4.1. Генерация перестановки по номеру.
        Практика:
[Перестановка по номеру]
    4.2. Получения номера по перестановке
        Практика:
[Перестановка по номеру]

5. Буквометика
    Практика: [Футбол и математика]

четверг, 3 февраля 2011 г.

Видеозанятие #1. Малая автоматизация тестирования


Ранее уже был пост на эту тему. Но здесь наглядно видно, как это все работает. Грамотно говорить пока не научился. Но качество видео заметно улучшилось. Спасибо Сагунову Данилу, за консультацию.

вторник, 1 февраля 2011 г.

Дерево Фенвика (Fenwick tree)

Изумительная структура данных. Классический пример гениальной мысли.

Дерево Фенвика позволяет за O(log(N)) определять значение обратимой функции на интервале массива [L,R].

Обратимая функция:
1) Сумма на интервале    [L,R]
2) Минимум на интервале 
3) Максимум на интервале

Теория:

1) Статья Алексея Лахно
2) Статья Максима Иванова.

Осознать сам подход поможет это изображение:

Запомним два правила.
1) При добавлении нового элемента делаем подъем вверх

2) При подсчете суммы элементов в интервале [0,X] делаем спуск вниз

Реализация:

  1. vector<int> b(MAX_VALUE+1);
  2.  
  3. void add(int x, int delta) {
  4.   for (; x <= MAX_VALUE; x = x | (x + 1))
  5.     b[x] += delta;
  6. }
  7.  
  8. int sum(int x) {
  9.   int res = 0;
  10.   for (; x >= 0; x = (x & (x + 1)) - 1)
  11.     res += b[x];
  12.   return res;
  13. }
* This source code was highlighted with Source Code Highlighter.

Практика:
Задача: 1028 (acm.timus.ru)
Решение: здесь

P.S: Не забываем, что дерево Фенвика легко интерпретируется на многомерный случай

Карманная сортировка (Bucket_sort)

[Все сортировки]

Теория: Wikipedia + Кормен[п.8.4. Второе издание]

Практика: informatics.mccme.ru

Реализация:

  1. const int MAX_VALUE = 2000; // значения массива [0, MAX_VALUE]
  2. const int BUCKETS = 10;     // количество карманов
  3. ...
  4. void bucket_sort(vector<int> &mas) {
  5.   vector<list<int> > mem(BUCKETS);
  6.   for (int i=0;i<mas.size();i++) {
  7.     int pos = (mas[i] - 1) / (MAX_VALUE / BUCKETS);
  8.     list<int>::iterator it = mem[pos].begin();
  9.     while (it != mem[pos].end() && *it < mas[i])
  10.       it++;
  11.     mem[pos].insert(it,mas[i]);
  12.   }
  13.   int pos = 0;
  14.   for (int i=0;i<BUCKETS;i++) {
  15.     for(list<int>::iterator it = mem[i].begin();it!= mem[i].end();it++)
  16.     {
  17.       mas[pos++] = *it;
  18.     }
  19.   }
  20. }
* This source code was highlighted with Source Code Highlighter.