Stampa di una combinazione valida di parentesi in python

Question

Sto provando a stampare tutte le combinazioni valide di parentesi in python usando la mia intuizione. Ha quasi funzionato, ma solo che non stampa poche combinazioni. Il codice è simile al seguente

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) 

Per n = 3, stampa

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

Funziona così.

Nella prima iterazione

()()() saranno stampate, quando la chiamata ritorna al padre immediato, sarà fetta della lista in cui ha iniziato a accodare prima che sarà ora() e eseguire la prossima iterazione del ciclo per la stampa() (()) e così via

il problema è che non sono in qualche modo in grado di catturare questa combinazione usando questa logica

(()())

Mentre sto pensando a come aggiustarlo, se c'è qualche pitone n guru può suggerire una soluzione a questo, allora sarà fantastico. Ci sono soluzioni alternative, ma poiché sono arrivato molto vicino, voglio migliorare il mio.

Answer 1

Penso che la tua versione corrente della logica sia un po 'semplificata per cogliere tutte le possibilità.

Questo problema si riduce a 3 casi diversi:

1. Abbiamo usato tutti i nostri parentesi aperte e solo bisogno di chiuderle
2. Non abbiamo nessun parentesi attualmente aperte ed è necessario aggiungere uno prima di chiudere di nuovo
3. Ne abbiamo almeno uno aperto e possiamo aprirne uno nuovo o chiuderlo.

seguire quella logica, abbiamo quindi bisogno di tenere traccia del numero di parentesi aperte abbiamo lasciato usare (no sotto), la stringa corrente di parentesi, e l'attuale equilibrio di vs. aperta chiusa (curb qui di seguito):

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

Questo mi sembra un uso naturale di memoization. parenthesis(10) coinvolgerà parentheses(6) e parentheses(4), ma parentheses(9) sarà anche coinvolgere parentheses(6) - così parenthesis(6) deve solo essere calcolato una volta. Inoltre, è naturale usare insiemi poiché ciò impedisce ad es. ()()() da contare due volte, una volta come () +()() e una volta come ()() +().Questo porta alla seguente codice, che sia schiaffeggia un nuovo paio di parentesi attorno parentesi generati per n-1 o concatena i risultati di due precedenti inviti:

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 

Ad esempio,

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

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