Всем доброго времени суток!
Эта коротенькая заметка посвящена симпатичной задачке генерации в лексикографическом порядке всех правильных скобочных последовательностей. Её нередко включают в список задач для подготовки к собеседованию (например, здесь).
По просторам инета гуляет следующее решение:
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")В итоге глубина рекурсии снизилась более чем в два раза :)
Комментарии (12)
ialexander
20.06.2023 16:25+6А вы тестировать пробовали? Вот результат работы gen_parentheses_v1 для parentheses_count = 3:
(()))
()())
()))
)))
Кстати, условия задачи я бы тоже порекомендовал включить в текст - так как ваша ссылка требует аутентификации, а после аутентификации предлагает "стартовать виртуальное соревнование".
К слову говоря, бага и в gen_parentheses сразу видна, там return в самом начале функции. Подозреваю и в gen_parentheses_v1 проблемы с отступами. Ну да, похоже у else некорректный отступ.
shoenfield Автор
20.06.2023 16:25Доброе утро! Огромное спасибо! Когда набивал заметку на Хабре, накосячил с отступами :) Поправил
Zara6502
20.06.2023 16:25+1В статье нет самой задачи, поэтому непосвящённым непонятна суть телодвижений.
Alexandroppolus
20.06.2023 16:25+2Судя по коду, генерация всех правильных скобочных последовательностей длины 2*n
domix32
20.06.2023 16:25+2Дано число n. Необходимо сгенерировать строки длинной 2*n с валидными перестановками открывающих и закрывающих скобок.
n = 3 // валидные ()()() ()(()) (())() ((())) // не валидные )(())( )))))) ((()() ...Закономерно решается через рекурсивные функции.
Alexandroppolus
20.06.2023 16:25+6В итоге глубина рекурсии снизилась более чем в два раза
Если уж тут начали бороться с рекурсией, то в оной борьбе надо идти до конца! )) Вот исходный вариант, переделанный на цикл самым простым и тупым способом:
Код
function genParentheses(n) { const arr = []; const stack = [-1]; let left = 0, right = 0; let action = 0; while (action >= 0) { switch(action) { case 0: if (left === n && right === n) { console.log(arr.join('')); action = stack.pop(); } else { action = 1; } break; case 1: if (left < n) { arr.push('('); left++; stack.push(2); action = 0; } else { action = 3; } break; case 2: left--; arr.pop(); action = 3; break; case 3: if (right < left) { arr.push(')'); right++; stack.push(4); action = 0; } else { action = stack.pop();; } break; case 4: right--; arr.pop(); action = stack.pop();; break; } } } genParentheses(3);Можно скопипастить в консоль браузера и там вызвать
mrCOTOHA
20.06.2023 16:25Если это перевести на ЯП топикстартера - получится не очень хорошо. Свитч (точнее match) пока тормозной в питоне. Я из-за него не смог, однажды, в Яндексовской задачке по времени уложиться :( Лучше на if ... elif заменить.
volatilization
20.06.2023 16:25Если честно, не понял вывода об уменьшении глубины рекурсии. Разве глубина не зависит от входящего параметра чуть ли не линейно? Ну и вроде бы параметры линейно меняются в последующих вызовах.
Alexandroppolus
20.06.2023 16:25В исходном варианте рекурсия глубиной 2N, поскольку каждый рекурсивный вызов увеличивает на 1 либо left, либо right, пока оба не вырастут с 0 до N. А в итоговом решении на каждом уровне рекурсии right на 1 больше, а left не менее чем right-1, итого на глубине N+1 достигается граница рекурсии left == N.
N - это parentheses_count, количество открывающих скобок.
dyadyaSerezha
И ни одного типа у параметров или возврата функции...