Генерация скобочных последовательностей
Дано целое число n . Требуется вывести все правильные скобочные последовательности длины 2 ⋅ n , упорядоченные лексикографически (см. https://ru.wikipedia.org/wiki/Лексикографический_порядок).
В задаче используются только круглые скобки.
Желательно получить решение, которое работает за время, пропорциональное общему количеству правильных скобочных последовательностей в ответе, и при этом использует объём памяти, пропорциональный n .
Формат ввода
Единственная строка входного файла содержит целое число n , 0 ≤ n ≤ 11
Формат вывода
Выходной файл содержит сгенерированные правильные скобочные последовательности, упорядоченные лексикографически.
Пример 1
Пример 2
import sys n = int(sys.stdin.readline()) def bracket(count, s='', left=0, right=0): if left == count and right == count: print(s) else: if left < count: bracket(count, s + '(', left+1, right) if right < left: bracket(count, s + ')', left, right+1) bracket(n) - Алгоритмы
- Сумма квадратов чисел
- Числа Фибоначи
- Dfs — обход графа в глубину
- Bfs — алгоритм обхода графа в ширину
- Сортировка улиткой
- НОД — нахождение наибольшего общего делителя для 2 чисел
- Покрытие точек отрезками
- Задача о выборе заявок
- Алгоритмы сортировки
- Куча
- Генерация скобочных последовательностей
- Анаграммы
- Одновременное итерирование по нескольким последовательностям
- Дескрипторы
- Паттерны проектирования
- Паттерн Decorator — python
- Паттерн Адаптер — Python
- Паттерн наблюдатель — Python
- Паттерн Абстрактная фабрика — python
- Настраиваем Celery в Django проекте
- Основные Linux команды
- Docker базовая инструкция
О генерации скобочных последовательностей
Эта коротенькая заметка посвящена симпатичной задачке генерации в лексикографическом порядке всех правильных скобочных последовательностей. Её нередко включают в список задач для подготовки к собеседованию (например, здесь).
По просторам инета гуляет следующее решение:
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")В итоге глубина рекурсии снизилась более чем в два раза 🙂
Генерация скобочных последовательностей
Привет, помогите разобраться, как решить задачу с помощью цикла. Есть решение с помощью рекурсии, но я хочу разобраться, как решить именно циклом.
Дано целое число n. Требуется вывести все правильные скобочные последовательности длины 2 ⋅ n, упорядоченные лексикографически
В задаче используются только круглые скобки.1 2 3 4 5 6 7 8 9 10 11 12
def bracket(count, s='', left=0, right=0): if left == count and right == count: print(s) else: if left count: bracket(count, s + '(', left + 1, right) if right left: bracket(count, s + ')', left, right + 1) n = int(input()) bracket(n)
Вывести количество допустимых скобочных последовательностей
Дана последовательность из символов '(', ')' и '?'. Символ '?' можно заменять на любую скобку.
Генерация последовательностей
Мне надо сгенерировать все последовательности длиной n состоящие из 0 и 1. Как я могу это сделать?Посчитать количество всех возможных правильных круглых скобочных последовательностей длиной n
Дано четное число n. Необходимо посчитать количество всех возможных правильных круглых скобочных.Генерация правильных скобочных последовательностей
Здравствуйте. Помогите, пожалуйста, написать программу на языке lisp, которая строит все правильные.Генерация правильных скобочных последовательностей
Доброго времени суток. Есть задача - сгенерировать все правильные скобочные последовательности.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
n = int(input()) n *= 2 for mask in range(1 n): balance, is_good, answer = 0, True, '' for bit in range(n): if (mask >> bit) & 1: balance += 1 answer += '(' else: balance -= 1 if balance 0: is_good = False break answer += ')' if is_good and balance == 0: print(answer)
Определить правильность скобочных последовательностей в файле
Коллеги, некорректно отрабатывает алгоритм, помогите пожалуйста Программа должна считывать из.Получить список всех правильных скобочных последовательностей
Правильная скобочная последовательность — это такая последовательность, которая могла быть.Найти количество правильных скобочных последовательностей из n скобок, где n четное число.
Найти количество правильных скобочных последовательностей из n скобок, где n четное число.Мне нужно найти алгоритм нахождения числа неправильных скобочных последовательностей из 1 правильной
Мне нужен алгоритм в котором из правильносй скобочной последовательности я смогу удаляя идущие.Рекурсия: генерация правильных скобочных структур длины 2n
Привет , уважаемые форумчане! Рекурсия и Рекурсивные алгоритмы! Искал данное задание негде нету .
