Всем доброго времени суток!
Эта коротенькая заметка посвящена симпатичной задачке генерации в лексикографическом порядке всех правильных скобочных последовательностей. Её нередко включают в список задач для подготовки к собеседованию (например, здесь).
По просторам инета гуляет следующее решение:
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")В итоге глубина рекурсии снизилась более чем в два раза :)
