Правильная скобочная последовательность

Когда-то однажды я встретил классическую задачу с правильной скобочной последовательностью. Задача звучала как-то так: «Сгенерировать k-ю в лексикографическом порядке правильную скобочную последовательность длины 2n». Эта была одна из первых задач на алгоритмы, которую я встретил. До сих пор не понимаю общепринятое решение, потому придумал свое. Эта статья про это самое решение.

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

Для длины n = 2

()

Для длины n = 4

(())
()()

Для длины n = 6

((()))
(()())
(())()
()(())
()()()

Для длины n = 8

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

Условимся называть скобочную последовательность просто СП, а правильную скобочную последовательность ПСП. Допустим, СП длины 2n содержитПСП. Тогда заметим, что для длины 2(n+1) в лексикографическом порядке последние ПСП в точности равны ПСП длины 2n в начало которых добавлен (). Если еще немного поднапрячься, можно заметить, что, если предыдущая за ней группа начинается с (()…, а если исключить оттуда (), получаемая группа соответствует ПСП длине 2n. Приходим к гипотезе, в которой следующая группа получается добавлением () между групп, начинающихся с (((…(((.

Данная статья не о ее доказательстве, так что этот момент я пропущу и сразу приступлю к реализации. Моя реализация учитывает обратный порядок сортировки ПСП, но это не сложно будет исправить, изменив «k-тый с начала» на «k-тый с конца», учитывая посчитанное количество всех ПСП. Посчитаем, сколько групп начинаются с одной (, двумя ((, тремя ((( и так далее скобками и впишем в матрицу.

1: 000 001
2: 000 001 002
3: 000 002 004 005
4: 000 005 010 013 014
5: 000 014 028 037 041 42
6: 000 042 084 112 126 131 132
7: 000 132 264 354 402 422 428 429

Эта информация поможет узнать по числу k со скольких скобочек он начинается. А точнее, по какому индексу произошла последняя «вставка» элементарной СП (). Тогда мы можем откатиться на массив вверх и проделать тоже самое для ПСП меньшего размера. После завершения программы у нас будет массив «вставок», с помощью которого легко решить вопрос за O(n^2).

Сразу же находим алгоритм поиска этих чисел:
f[n+1][0]=0
f[n+1][1]=f[n].last
f[n+1][k]= f[n + 1][k-1] + f[n + 1][1] — f[n][k-2]

Код на swift:

var array = (1...n + 1).map { Array(repeating: 0, count: $0) } array[1][1] = 1 for i in (2...n) {     array[i][1] = array[i - 1][i - 1]     for j in 2...i {         array[i][j] = array[i][1] + array[i][j - 1] - array[i - 1][j - 2]     } }

var array = Array(repeating: 0, count: n + 1) var (l, r) = (0, 1) for i in 2...n {     (l, array[1]) = (0, r)     for j in 2...i {         let m = r - l + array[j - 1]         l = array[0]         array[0] = array[j]         array[j] = m     }     (array[0], r) = (array[1], array[i]) } array[0] = 0

Напишем бинарный поиск, для поиска номера вставки по заданному k:

var (l, r) = (-1, n + 1) while r - l > 1 {     let m = l + (r - l) / 2     if array[n][m] <= k {         l = m     } else {         r = m     } }

Чтобы откатиться на СП меньшего размера, нужно так же откатить и значение k. Если на этой итерации мы поняли, что требуется l-тая вставка, те, имеется хотя бы l открывающих скобок, то на следующей итерации будет хотя бы l-1 открывающих скобок, значит, нужно исключить array[n][l] и учитывать array[n — 1][l — 1] скобок. Возможно, будет так, что l = 0, тогда k не должен изменяться.

var inserts = Array(repeating: 0, count: n) for i in (1...n).reversed() {     var (l, r) = (-1, i + 1)     while r - l > 1 {         let m = l + (r - l) / 2         if array[i][m] <= k {             l = m         } else {             r = m         }     }     inserts[i - 1] = l     k = k - (l > 0 ? array[i][l] - array[i - 1][l - 1] : 0) }

Бинарный поиск можно ускорить, если начинать не с 0, а с l, прервать внешний цикл, если попасть в последний элемент и другое. Но здесь я лишь пытаюсь продемонстрировать идею. По-этому, так же продемонстрирую тривиальное решение преобразования массива вставок в СП за O(n^2):

var res: [Character] = [] for i in inserts {     res.insert(contentsOf: ["(", ")"], at: i) }  print(String(res))

Можно сделать, конечно же, лучше. Если создать массив открытых скобок длины 2n и закрывать скобки по мере возможности, создание СП выполнится за O(n).

var res: [Character] = Array(repeating: "(", count: 2 * n) var j = 0 var c = 0 for i in (1..<2 * n).reversed() {     if inserts[j] == c {         res[i] = ")"         j += 1         c += 1     } else {         c -= 1     } }

В итоге общая сложность оценивается в O(n^2) на память и O(n log n) на выполнение(если не учитывать время на генерацию таблицы, например, если заданы не пара (n, k), а множество таких пар). Можно так же реализовать за O(n) на память и O(n^2log n) на выполнение, что хуже классического результата. Используя этот алгоритм, основанный на массиве вставок, для нахождения номера по ПСП, а не наоборот, получается уже лучший результат, чем классический: O(n^2) на память и O(n) на выполнение или O(n) на память и O(n^2) на выполнение. Причем памяти требуется меньше даже в случае O(n^2).

let vbs = Array("(()(()())...())") let n = vbs.count / 2  var array = (1...n + 1).map { Array(repeating: 0, count: $0) } array[1][1] = 1 for i in (2...n) {     array[i][1] = array[i - 1][i - 1]     for j in 2...i {         array[i][j] = array[i][1] + array[i][j - 1] - array[i - 1][j - 2]     } }  var inserts = Array(repeating: 0, count: n)  var k = 0 var j = n - 1 for i in 0..<2 * n {     if vbs[i] == "(" {         k += 1     } else {         k -= 1         inserts[j] = k         j -= 1     } }  var m = 0 for i in (1...n).reversed() {     let ii = inserts[i - 1]     m += ii > 0 ? array[i][ii] - array[i - 1][ii - 1] : 0 }  print(array[n][n] - (m + 1))