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

Всем доброго времени суток!

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

По просторам инета гуляет следующее решение:

def  gen_parentheses(parentheses_count, str_, left, right, out_file):     if left == parentheses_count and right == parentheses_count:         out_file.write(str_ + "\n")     return     if left < parentheses_count:         gen_parentheses(parentheses_count, str_ + "(", left + 1, right, out_file)     if right < left:         gen_parentheses(parentheses_count, str_ + ")", left, right + 1, out_file)  with open("input.txt") as in_file:     parentheses_count = int(next(in_file)) with open("output.txt", "w") as out_file:     gen_parentheses(parentheses_count, "", 0, 0, out_file)

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

Ну, во-первых, очевидно, что если число добавленных открывающихся скобок достигло заданного, то нет смысла добавлять соответствующие закрывающиеся скобки по одной – можно сразу добавить все недостающие закрывающиеся скобки:

def  gen_parentheses_v1(parentheses_count, str_, left, right, out_file):     if left < parentheses_count:         gen_parentheses_v1(parentheses_count, str_ + "(", left + 1, right, out_file)         if right < left:             gen_parentheses_v1(parentheses_count, str_ + ")", left, right + 1, out_file)         else:             out_file.write(str_ + (parentheses_count-right)*")" + "\n")

А во-вторых, да и с открывающимися скобками можно не тормозить 🙂 – добавлять не по одной, а сразу строкой из нескольких открывающихся скобок и одной закрывающейся:

def gen_parentheses_v2(parentheses_count, str_, left, right, out_file):     if left < parentheses_count:         for i in range(parentheses_count, max(left, right+1) - 1, -1):               gen_parentheses_v2(parentheses_count,                                str_ + (i-left)*"(" + ")",                                i,                                right + 1,                                out_file)     else:         out_file.write(str_ + (parentheses_count-right)*")" + "\n")

В итоге глубина рекурсии снизилась более чем в два раза 🙂