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

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

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

Для длины n = 2

()

Для длины n = 4

(())
()()

Для длины n = 6

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

Для длины n = 8

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

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

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

1: 0 1
2: 0 1 2
3: 0 2 4 5
4: 0 5 10 13 14
5: 0 14 28 37 41 42
6: 0 42 84 112 126 131 132
7: 0 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))