e-maxx_algo

for (int i=0; i<=k; ++i)

ans += d[n*2-1][i] * d[n*2-2][k-i]; cout << ans;

Нахождение всех последовательностей

Иногда требуется найти и вывести все правильные скобочные последовательности указанной длины (в данном случае — это длина строки).

каждый раз лексикографически следующую последовательность с помощью алгоритма, описанного в следующем разделе.

Но если ограничения не очень большие ( до ), то можно поступить значительно проще. Найдём всевозможные перестановки этих скобок (для этого удобно использовать функцию next_permutation()), их будет ,

и каждую проверим на правильность вышеописанным алгоритмом, и в случае правильности выведем текущую последовательность.

Также процесс нахождения всех последовательностей можно оформить в виде рекурсивного перебора с отсечениями (что в идеале можно довести по скорости работы до первого алгоритма).

Нахождение следующей последовательности

Здесь рассматривается только случай одного типа скобок.

По заданной правильной скобочной последовательности требуется найти правильную скобочную последовательность, которая находится следующей в лексикографическом порядке после текущей (или выдать "No solution", если такой не существует).

Понятно, что в целом алгоритм выглядит следующим образом: найдем такую самую правую открывающую скобку, которую мы имеем право заменить на закрывающую (так, чтобы в этом месте правильность не нарушалась), а всю оставшуюся справа строку заменим на лексикографически минимальную: т.е. сколько-то открывающих скобок, затем все оставшиеся закрывающие скобки. Иными словами, мы пытаемся оставить без изменения как можно более длинный префикс исходной последовательности, а в суффиксе эту последовательность заменяем на лексикографически минимальную.

Осталось научиться искать эту самую позицию первого изменения. Для этого будем идти по строке справа налево

а баланс после обработки этого символа больше нуля, то мы нашли самую правую позицию, от которой мы можем начать изменять последовательность (в самом деле, означает, что слева имеется не закрытая ещё

скобка). Поставим в текущую позицию закрывающую скобку, затем максимально возможное количество открывающих скобок, а затем все оставшиеся закрывающие скобки, — ответ найден.

Если мы просмотрели всю строку и так и не нашли подходящую позицию, то текущая последовательность — максимальна, и ответа не существует.

Реализация алгоритма:

string s; cin >> s;

int n = (int) s.length(); string ans = "No solution";

for (int i=n-1, depth=0; i>=0; --i) { if (s[i] == '(')

--depth;

else

++depth;

if (s[i] == '(' && depth > 0) { --depth;

int open = (n-i-1 - depth) / 2; int close = n-i-1 - open;

ans = s.substr(0,i) + ')' + string ('(', open) + string

(')', close);

break;

}

}

cout << ans;

Таким образом, мы решили эту задачу за .

Номер последовательности

Здесь пусть — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.

Научимся считать вспомогательную динамику , где — длина скобочной последовательности

(она "полуправильна": всякой закрывающей скобке имеется парная открывающая, но не все открытые скобки закрыты),

— баланс (т.е. разность между количеством открывающих и закрывающих скобок), — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.

мысленно переберём, чему был равен последний символ этой последовательности. Если он был равен '(', то до этого символа мы находились в состоянии . Если он был равен ')', то предыдущим было

состояние . Таким образом, получаем формулу:

Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких

скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет пар) могут быть любого из типов, поэтому

ответ умножается на эту степень числа .

Нахождение -ой последовательности

Здесь пусть — количество пар скобок в последовательности. В данной задаче по заданному требуется найти - ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.

Как и в предыдущем разделе, посчитаем динамику — количество правильных скобочных последовательностей длины с балансом .

Пусть сначала допустимы только скобки одного типа.

Будем двигаться по символам искомой строки, с -го по -ый. Как и в предыдущей задаче, будем хранить счётчик — текущую глубину вложенности в скобки. В каждой текущей позиции будем перебирать

возможный символ - открывающую скобку или закрывающую. Пусть мы хотим поставить сюда открывающую скобку,

конце концов мы и получим искомую скобочную последовательность. Реализация на языке Java с использованием длинной арифметики:

int n; BigInteger k; // входные данные

BigInteger d[][] = new BigInteger [n*2+1][n+1]; for (int i=0; i<=n*2; ++i)

for (int j=0; j<=n; ++j)

d[i][j] = BigInteger.ZERO; d[0][0] = BigInteger.ONE;

for (int i=0; i<n*2; ++i)

for (int j=0; j<=n; ++j) { if (j+1 <= n)

d[i+1][j+1] = d[i+1][j+1].add( d[i][j] ); if (j > 0)

d[i+1][j-1] = d[i+1][j-1].add( d[i][j] );

}

String ans = new String();

if (k.compareTo( d[n*2][0] ) > 0) ans = "No solution";

else {

int depth = 0;

for (int i=n*2-1; i>=0; --i)

if (depth+1 <= n && d[i][depth+1].compareTo( k ) >= 0) { ans += '(';

++depth;

}

else {

ans += ')';

if (depth+1 <= n)

k = k.subtract( d[i][depth+1] );

--depth;

}

}

Пусть теперь разрешён не один, а типов скобок. Тогда алгоритм решения будет отличаться от предыдущего

для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем). Реализация на языке Java для случая двух типов скобок - круглых и квадратных:

int n; BigInteger k; // входные данные

BigInteger d[][] = new BigInteger [n*2+1][n+1]; for (int i=0; i<=n*2; ++i)

for (int j=0; j<=n; ++j)

d[i][j] = BigInteger.ZERO; d[0][0] = BigInteger.ONE;

for (int i=0; i<n*2; ++i)

for (int j=0; j<=n; ++j) { if (j+1 <= n)

d[i+1][j+1] = d[i+1][j+1].add( d[i][j] ); if (j > 0)

d[i+1][j-1] = d[i+1][j-1].add( d[i][j] );

}

String ans = new String(); int depth = 0;

char [] stack = new char[n*2]; int stacksz = 0;

for (int i=n*2-1; i>=0; --i) { BigInteger cur;

// '('

if (depth+1 <= n)

cur = d[i][depth+1].shiftLeft( (i-depth-1)/2 );

else

cur = BigInteger.ZERO; if (cur.compareTo( k ) >= 0) {

ans += '('; stack[stacksz++] = '('; ++depth;

continue;

}

k = k.subtract( cur );

// ')'

if (stacksz > 0 && stack[stacksz-1] == '(' && depth-1 >= 0) cur = d[i][depth-1].shiftLeft( (i-depth+1)/2 );

else

cur = BigInteger.ZERO; if (cur.compareTo( k ) >= 0) {

ans += ')'; --stacksz; --depth; continue;

}

k = k.subtract( cur ); // '['

if (depth+1 <= n)

cur = d[i][depth+1].shiftLeft( (i-depth-1)/2 );

else

cur = BigInteger.ZERO; if (cur.compareTo( k ) >= 0) {

ans += '['; stack[stacksz++] = '['; ++depth;

continue;

}

k = k.subtract( cur ); // ']'

ans += ']'; --stacksz; --depth;

}

Количество помеченных графов

на неориентированности графа и отсутствии петель). Тогда множество всех возможных рёбер графа имеет мощность

, т.е. .

Поскольку любой помеченный граф однозначно определяется своими рёбрами, то количество помеченных графов с вершинами равно:

Количество связных помеченных графов

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

Научимся, наоборот, считать количество несвязных графов; тогда количество связных графов получится как минус найденное число. Более того, научимся считать количество корневых (т.е. с выделенной вершиной

- корнем) несвязных графов; тогда количество несвязных графов будет получаться из него делением на

. Заметим, что, так как граф несвязный, то в нём найдётся компонента связности, внутри которой лежит корень, а остальной граф будет представлять собой ещё несколько (как минимум одну) компонент связности.

выделить корень в компоненте связности из вершин равно . Итого, при фиксированном количество

корневых несвязных графов равно:

Значит, количество несвязных графов с вершинами равно:

Наконец, искомое количество связных графов равно:

Количество помеченных графов с компонентами связности

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

количество помеченных графов с вершинами и компонентами связности.

Научимся вычислять очередной элемент , зная предыдущие значения. Воспользуемся стандартным

приёмом при решении таких задач: возьмём вершину с номером 1, она принадлежит какой-то компоненте, вот эту компоненту мы и будем перебирать. Переберём размер этой компоненты, тогда количество способов выбрать

такое множество вершин равно (одну вершину — вершину 1 — перебирать не надо). Количество же

Итого получаем примерно такой код:

int d[n+1][k+1]; // изначально заполнен нулями d[0][0][0] = 1;

for (int i=1; i<=n; ++i)

for (int j=1; j<=i && j<=k; ++j) for (int s=1; s<=i; ++s)

d[i][j] += C[i-1][s-1] * conn[s] * d[i-s][j-1];

cout << d[n][k][n];

Разумеется, на практике, скорее всего, нужна будет длинная арифметика.

Генерация сочетаний из N элементов

Сочетания из N элементов по K в лексикографическом порядке

Постановка задачи. Даны натуральные числа N и K. Рассмотрим множество чисел от 1 до N. Требуется вывести все различные его подмножества мощности K, причём в лексикографическом порядке.

Алгоритм весьма прост. Первым сочетанием, очевидно, будет сочетание (1,2,...,K). Научимся для текущего сочетания находить лексикографически следующее. Для этого в текущем сочетании найдём самый правый элемент, не достигший ещё своего наибольшего значения; тогда увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения.

bool next_combination (vector<int> & a, int n) { int k = (int)a.size();

for (int i=k-1; i>=0; --i) if (a[i] < n-k+i+1) {

++a[i];

for (int j=i+1; j<k; ++j) a[j] = a[j-1]+1;

return true;

}

return false;

}

С точки зрения производительности, этот алгоритм линеен (в среднем), если K не близко к N (т.е. если не выполняется, что K = N - o(N)). Для этого достаточно доказать, что сравнения "a[i] < n-k+i+1" выполняются в сумме Cn+1k раз, т.е. в (N

+1) / (N-K+1) раз больше, чем всего есть сочетаний из N элементов по K.

Сочетания из N элементов по K с изменениями ровно одного элемента

Требуется выписать все сочетания из N элементов по K, но в таком порядке, что любые два соседних сочетания будут отличаться ровно одним элементом.

Интуитивно можно сразу заметить, что эта задача похожа на задачу генерации всех подмножеств данного множества в таком порядке, когда два соседних подмножества отличаются ровно одним элементом. Эта задача непосредственно решается с помощью Кода Грея: если мы каждому подмножеству поставим в соответствие

битовую маску, то, генерируя с помощью кодов Грея эти битовые маски, мы и получим ответ.

Может показаться удивительным, но задача генерации сочетаний также непосредственно решается с помощью

кода Грея. А именно, сгенерируем коды Грея для чисел от 0 до 2N-1, и оставим только те коды, которые содержат ровно K единиц. Удивительный факт заключается в том, что в полученной последовательности любые

две соседние маски (а также первая и последняя маски) будут отличаться ровно двумя битами, что нам как раз и требуется.

Докажем это.

Для доказательства вспомним факт, что последовательность G(N) кодов Грея можно получить следующим образом:

G(N) = 0G(N-1) 1G(N-1)R

т.е. берём последовательность кодов Грея для N-1, дописываем в начало каждой маски 0, добавляем к ответу; затем снова берём последовательность кодов Грея для N-1, инвертируем её, дописываем в начало каждой маски 1 и добавляем к ответу.

Теперь мы можем произвести доказательство.

Сначала докажем, что первая и последняя маски будут отличаться ровно в двух битах. Для этого достаточно заметить, что первая маска будет иметь вид N-K нулей и K единиц, а последняя маска будет иметь вид: единица, потом N-K-1 нулей, потом K-1 единица. Доказать это легко по индукции по N, пользуясь приведённой выше формулой

для последовательности кодов Грея.

Теперь докажем, что любые два соседних кода будут отличаться ровно в двух битах. Для этого снова обратимся к формуле для последовательности кодов Грея. Пусть внутри каждой из половинок (образованных из G(N-1))

утверждение верно, докажем, что оно верно для всей последовательности. Для этого достаточно доказать, что оно верно в месте "склеивания" двух половинок G(N-1), а это легко показать, основываясь на том, что мы знаем первый и последний элементы этих половинок.

Приведём теперь наивную реализацию, работающую за 2N:

int gray_code (int n) { return n ^ (n >> 1);

}

int count_bits (int n) { int res = 0; for (; n; n>>=1)

res += n & 1; return res;

}

void all_combinations (int n, int k) { for (int i=0; i<(1<<n); ++i) {

int cur = gray_code (i);

if (count_bits (cur) == k) { for (int j=0; j<n; ++j)

if (cur & (1<<j))

printf ("%d ", j+1);

puts ("");

}

}

}

Стоит заметить, что возможна и в некотором смысле более эффективная реализация, которая будет строить всевозможные сочетания на ходу, и тем самым работать за O (Cnk n). С другой стороны, эта

реализация представляет собой рекурсивную функцию, и поэтому для небольших n, вероятно, она имеет большую скрытую константу, чем предыдущее решение.

Собственно сама реализация - это непосредственное следование формуле:

G(N,K) = 0G(N-1,K) 1G(N-1,K-1)R

Эта формула легко получается из приведённой выше формулы для последовательности Грея - мы просто выбираем подпоследовательность из подходящих нам элементов.

bool ans[MAXN];

void gen (int n, int k, int l, int r, bool rev) { if (k > n || k < 0) return;

if (!n) {

for (int i=0; i<n; ++i)

printf ("%d", (int)ans[i]); puts ("");

return;

}

ans[rev?r:l] = false;

gen (n-1, k, !rev?l+1:l, !rev?r:r-1, rev); ans[rev?r:l] = true;

gen (n-1, k-1, !rev?l+1:l, !rev?r:r-1, !rev);

}

void all_combinations (int n, int k) { gen (n, k, 0, n-1, false);

}