So I am writing a function which returns a list of strings of all the legal parentheses in which exactly n pairs of parentheses were opened and closed. The bracket types are given as strings in the pairs list.

For example: if pairs are the list ["()", "[]"] the function must return all valid 2n character expressions with square brackets and round brackets.

Note: Bracket expression is valid if all opened brackets are also closed (with the appropriate bracket) and if the brackets are nested correctly in each other. "[] ()" Is a valid expression, while "[(])" is not a valid expression.

For example: Input:

print(all_paren(2, ["()","{}"]))

Should return the following list:

['(())', '()()', '(){}', '({})', '{()}', '{{}}', '{}()', '{}{}']

My code without much success:

def all_paren(n, pairs):
    lst = []
    for i in range(len(pairs)):
        lst1 = []
        generateParentheses(0,0,n,pairs[i][0],pairs[i][1],lst1)
        lst.extend(lst1)
    return lst

def generateParentheses(openBr, closeBr, n, left_bracket, right_bracket,lst,s=[]):
    if closeBr == n:
        lst.append(''.join(s))
        return 

    if closeBr < openBr:
        s.append(right_bracket)
        generateParentheses(openBr, closeBr 1, n,left_bracket,right_bracket,lst,s)
        s.pop()
    if openBr < n:
        s.append(left_bracket)
        generateParentheses(openBr 1, closeBr, n,left_bracket,right_bracket,lst,s)
        s.pop()
    return

Thanks in advance!

CodePudding user response：

Use permutations method build into python through itertools

open_close and close_open are dictionaries open_close maps open brackets to close brackets and close_open maps close brackets to open brackets.

all_perm() generates all permutations for supplied brackets .

is_val_paren takes a string and checks weather the parenthesis combination is valid or not.

import itertools

open_close = dict(
        {'(':')',
            '[':']',
            '{':'}',
            '<':'>'
            }
        )
close_open = dict(
        {')':'(',
            ']':'[',
            '}':'{',
            '>':'<'
            }
        )

def all_perm(n, values):
    valid_parens = []

    for parens in itertools.product(values, repeat = n):
        val = list()
        for v in parens:
            val.extend(v)
        #print(f"{val}")
        for perm in itertools.permutations(range(n*2)):
            brakets = [None]*(n*2)
            for index, p in enumerate(perm):
                brakets[index] = val[p] 
            #print(f"{perm=} {brakets=}")
            if is_val_paren(brakets):
                valid_parens.append(''.join(brakets))
    return set(valid_parens)

def is_val_paren(brakets:list):
    stack = list()
    for braket in brakets:
        if braket in open_close.keys():
            stack.append(braket)
        else:
            if len(stack) == 0:
                return False
            elif stack[-1] == close_open[braket]:
                stack.pop()
            else:
                return False
    return len(stack) == 0 

print(all_perm(n = 2, values = ["()", "[]"]))
print()
print(all_perm(n = 1, values = ["()", "[]"]))
print()
print(all_perm(n = 3, values = ["()", "[]", "{}"]))

output:

{'[()]', '()[]', '([])', '[]()', '[[]]', '()()', '[][]', '(())'}

{'[]', '()'}

{'([{}])', '{[]}()', '{[][]}', '{}[]{}', '[({})]', '[]{()}', '(())[]', '{({})}', '[()()]', '[][{}]', '()[{}]', '[()[]]', '[]()[]', '()[()]', '()(())', '()({})', '(([]))', '[(())]', '[([])]', '[{}][]', '(){}{}', '{[]()}', '{{{}}}', '({}[])', '({}){}', '([()])', '{}(){}', '{()()}', '[{{}}]', '[{}{}]', '[(){}]', '(){[]}', '()()[]', '{{}()}', '(){}()', '{}[{}]', '[](){}', '({{}})', '(()){}', '[][][]', '()[]{}', '({})[]', '{}{[]}', '{}[][]', '([]())', '{}[[]]', '[]{{}}', '({()})', '[]([])', '()()()', '[[()]]', '[[]()]', '[](())', '{}{{}}', '{[]{}}', '{}{}[]', '{{}}{}', '()[][]', '([])()', '[()][]', '[{}]{}', '{[[]]}', '([]){}', '{}[()]', '()[[]]', '[{}]()', '{[]}{}', '{{}[]}', '()[]()', '{}{}()', '{(){}}', '({[]})', '{{}{}}', '{()}{}', '[[]]()', '((){})', '[{}[]]', '[()]{}', '[]{}{}', '{{()}}', '([][])', '(()[])', '()([])', '{(())}', '[[]][]', '([]{})', '(())()', '([[]])', '[]{}[]', '[[[]]]', '(){}[]', '[[][]]', '[{}()]', '[][]()', '[[]]{}', '{}(())', '{}({})', '{[()]}', '[()]()', '(){()}', '{}([])', '(){{}}', '[]{}()', '{}()()', '[]()()', '([])[]', '{()}()', '{}{()}', '(({}))', '[[]{}]', '[][()]', '{}[]()', '({}{})', '((()))', '({})()', '{()}[]', '[[{}]]', '()(){}', '[][[]]', '{{}}()', '[{()}]', '{([])}', '[][]{}', '{{}}[]', '({}())', '[{[]}]', '{[{}]}', '{()[]}', '(()())', '{{[]}}', '[]{[]}', '{}()[]', '{}{}{}', '[]({})', '{[]}[]'}