Печать правильной комбинации круглых скобок в python

Question

Я пытаюсь напечатать всю действительную комбинацию круглых скобок в python, используя мою собственную интуицию. Он почти сработал, но просто он не печатает несколько комбинаций. Код выглядит следующим образом

solution = "" 

def parentheses(n): 

    global solution 

    if n == 0: 
     print solution 
     return 

    for i in range(1, n+1): 
     start_index = len(solution) 
     solution = solution + ("(" * i + ")" * i) 
     parentheses(n - i) 
     solution = solution[:start_index] 

if __name__ == "__main__": 
    n = int(raw_input("Enter the number of parentheses:")) 
    print "The possible ways to print these parentheses are ...." 
    parentheses(n) 

при п = 3, он печатает

()()()
() (())
(())()
((()))

Это работает именно так.

В первой итерации

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

проблемы в том, что я как-то не в состоянии захватить эту комбинацию, используя эту логику

(()())

Хотя я думаю о том, как исправить это, если какой-либо pytho Русский гуру может предложить исправить это, тогда это будет здорово. Существуют альтернативные решения, но, поскольку я подошел очень близко, я хочу улучшить свою работу.

Answer 1

Я думаю, что ваша текущая версия логики немного упрощена, чтобы захватить все возможности.

Эта проблема сводится к 3 различным случаям:

1. Мы использовали все наши открытые скобки и просто необходимы, чтобы закрыть их
2. У нас нет никакой открытой в данный момент скобки и нужно добавить один до закрытия снова
3. У нас есть хотя бы один открытый и может либо открыть новый, либо закрыть его.

Чтобы следовать этой логике, то нужно следить за количество открытых скобок мы оставили использовать (no ниже), текущую строку скобок и текущего баланс открытого VS. закрытого (curb ниже):

def parens(no, s="", curb=0): 
    # case 1: all open parens used 
    if no == 0: 
     if curb == 0: 
      return [s] 
     return parens(no, s+")", curb-1) 

    # case 2: none are currently open 
    if curb == 0: 
     return parens(no-1, s+"(", curb+1) 

    # case 3: one or more are currently open 
    return parens(no-1, s+"(", curb+1) + parens(no, s+")", curb-1) 

Answer 2

Это кажется естественным использование memoization. parenthesis(10) будет включать parentheses(6) и parentheses(4), но parentheses(9) будет также включать parentheses(6) - так parenthesis(6) следует просто вычислить один раз. Также - естественно использовать наборы, поскольку это предотвращает, например, ()()() от подсчета дважды, один раз как () +()() и один раз ()() +().Это приводит к следующему коду, который либо шлепает новую пару скобок вокруг круглых скобок, генерируемых для n-1 или сцепляет результаты двух предыдущих вызовов:

cache = {} 

def parentheses(n): 
    if n == 0: 
     return set(['']) 
    elif n in cache: 
     return cache[n] 
    else: 
     par = set('(' + p + ')' for p in parentheses(n-1)) 
     for k in range(1,n): 
      par.update(p+q for p in parentheses(k) for q in parentheses(n-k)) 
     cache[n] = par 
     return par 

Например,

>>> for p in parentheses(3): print(p) 

(()()) 
((())) 
()(()) 
()()() 
(())()