Генератор скобок

Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке – алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.

Помогите Рите – напишите программу, которая по заданному n выведет все ПСП в нужном порядке.

Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:

(())
()()

(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).

Формат ввода

На вход функция принимает n — целое число от 0 до 10.

Формат вывода

Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.

def gen_binary(control, n1, n2, prefix):
    if n1 == 0 and n2 == 0:
        print(prefix)
    else:
        if n1 > 0:
            gen_binary(control + 1, n1 - 1, n2, prefix + '(')
        if (control > 0 and n2 > 0):
            gen_binary(control - 1, n1, n2 - 1, prefix + ')') 


n = int(input())
control = 0
n1 = n
n2 = n
gen_binary(control, n1, n2, '')


Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Комментариев к записи: 1

  1. alf:

    Ваш код генерит все последовательности скобок. А надо только ПСП. Во втором if надо добавить если n1 < n2

Оставить комментарий