gen_bracket_seq.md

Генерация правильных скобочных последовательностей

| Главная | Алгебра |

Генерация скобочных последовательностей (анлг. generation all bracket sequences) — класс комбинаторных объектов, представляющих собой последовательность скобочных символов. Пусть нам известно число n. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с n открывающимися скобками.

Реализация

• Рекурсивный алгоритм

Время
O((Cnn/2 - Cnn/2 - 1) * n)

def generation(n, cnt_open=0, cnt_close=0, answer=''):
    if cnt_open + cnt_close == n:
        print(answer)
        return
    if cnt_open < n:
        generation(n, cnt_open + 1, cnt_close, answer + '(')
    if cnt_close < cnt_open:
        generation(n, cnt_open, cnt_close + 1, answer + ')')


generation(3) # ((())), (()()), (())(), ()(()), ()()()