Drukowanie prawidłowej kombinacji nawiasów w pytonie

Question

Próbuję wydrukować wszystkie prawidłowe kombinacje nawiasów w python za pomocą mojej własnej intuicji. To prawie działało, ale po prostu nie wydrukowało kilku kombinacji. Kod wygląda tak

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) 

dla N = 3, drukuje

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

To działa tak.

W pierwszej iteracji

()()() zostaną wydrukowane, kiedy powraca wezwanie do natychmiastowego rodzica, będzie kroić listy gdzie zaczęło dołączać pierwszy który będzie teraz() i uruchomienie kolejnej iteracji pętli do drukowania() (()) i tak dalej

problemem jest to, że nie jestem jakoś w stanie uchwycić to połączenie przy użyciu tej logiki

(()())

Podczas gdy myślę, jak to naprawić, jeśli jakieś pytho n guru może zaproponować poprawkę do tego, wtedy to będzie wspaniałe. Istnieją alternatywne rozwiązania, ale odkąd doszedłem bardzo blisko, chcę poprawić moje.

Answer 1

Myślę, że twoja obecna wersja logiki jest nieco zbyt uproszczona, aby uchwycić wszystkie możliwości.

Problem ten sprowadza się do 3 różnych przypadkach:

1. Użyliśmy wszystkich naszych otwartych nawiasów i wystarczy je zamknąć
2. Nie mamy żadnych aktualnie otwartych nawiasów i trzeba dodać jeden przed zamknięciem ponownie
3. Mamy co najmniej jeden otwarty i można otworzyć nowy lub zamknąć jeden.

Aby podążać tą logiką, my wtedy trzeba śledzić liczbę otwartych parens nam zostało do wykorzystania (no poniżej), aktualny ciąg parens i bieżącym bilansu zamknięcia Otwórz vs (curb poniżej):

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

Wydaje się to być naturalnym zastosowaniem memoization. parenthesis(10) będzie obejmował parentheses(6) i parentheses(4), alebędzie musiał być obliczony tylko jeden raz. Również - naturalne jest używanie zestawów, ponieważ uniemożliwia to np. ()()() z liczenia dwukrotnie, raz jako () +()() i raz jako ()() +().Prowadzi to do następującego kodu, które albo klepie nową parę nawiasów wokół nawiasach generowanych przez n-1 lub skleja wyniki dwóch poprzednich rozmów:

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 

Na przykład,

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

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