How to return all valid combinations of n-pairs of parentheses?

Question

def paren(n):
    lst = ['(' for x in range(n)]
    current_string = ''.join(lst)
    solutions = list()
    for i in range(len(current_string)+1):
        close(current_string, n, i, solutions)
    return solutions

def close(current_string, num_close_parens, index, solutions):
    """close parentheses recursively"""
    if num_close_parens == 0:
        if current_string not in solutions:
            solutions.append(current_string)
        return
    new_str = current_string[:index] + ')' + current_string[index:]
    if num_close_parens and is_valid(new_str[:index+1]):
        return close(new_str, num_close_parens-1, index+1, solutions)
    else:
        return close(current_string, num_close_parens, index+1, solutions)

def is_valid(part):
    """True if number of open parens >= number of close parens in given part"""
    count_open = 0
    count_close = 0
    for paren in part:
        if paren == '(':
            count_open += 1
        else:
            count_close += 1
    if count_open >= count_close:
        return True
    else:
        return False

print paren(3)

The above code is my attempt at solving the stated problem. It gives sufficient solutions for n<3, but otherwise, it doesn't give out all the solutions. For example, when n=3, it outputs ['()()()', '(())()', '((()))'] leaving out '()(())'. How do I modify the code to output all the possible solutions correctly?

Answer 1

Here is my solution

from itertools import permutations
n = 3
input = ("( " * n) + (") " * n)
in_list = [f for f in input.split(" ") if f]
possible_combinations = list(permutations(in_list, n*2))
valid_list = []

def ret_valid(el):
    num_open = num_close = 0
    for val in el:
        if val == "(":
            num_open += 1
        else:
            num_close += 1
        if num_close > num_open:
            return False
    return True

for el in possible_combinations:
    if ret_valid(el):
        if "".join(el) not in valid_list:
            valid_list.append("".join(el))
print(", ".join(valid_list))

Answer 2

I am new to dynamic programming and recursion, but here is my solution without recursion. Please let me know why it wont work or if this is an acceptable solution:

class Parenthesis(object):
    def __init__(self, parens):
        self.parens = parens
        self.my_valid_parens = {
                                1: ['()'],
                                2: ['()()', '(())']
                               }

    def generate_valid_paren(self):
        if self.parens <= 2:
            return self.my_valid_parens[self.parens] 

        i = 3
        while i <= self.parens:
            new_set = []
            for each in self.my_valid_parens[i-1]:
                new_set += set([each + '()', '()' + each, '(' + each + ')'])
            self.my_valid_parens[i] = list(new_set)
            i += 1

if __name__ == '__main__':
    num = 4
    p = Parenthesis(num)
    p.generate_valid_paren()
    print p.my_valid_parens[num]

Here is my output for when num = 3 and 4 respectively:

3: ['(()())', '()()()', '()(())', '(())()', '((()))']

4: ['(()())()', '()(()())', '((()()))', '()()()()', '(()()())', '()()(())', '(()(()))', '()(())()', '((())())', '(())()()', '()(())()', '()((()))', '(((())))', '((()))()']

Answer 3

For N==3, there are 5 valid combinations: ()()(), ((())), (()()), (())() and ()(()).

The recursive algorithm works like this:

• Build the valid strings from left to right by adding either one left or one right parentheses at a time.
• Base case: all left and all right parentheses have been used (left == n && right == n). Just return an empty string. Otherwise:
• Print a left parenthesis if not all of them have been used (left < n), and invoke the sub-problem with (n, left + 1, right)
• Print a right parentheses only if the number of used right parentheses is less than the number of used left parentheses (right < left). Invoke the sub-problem with (n, left, right + 1)

Here is the Java Code:

public static ArrayList<String> parentheses(int n, int left, int right) {

ArrayList<String> results = new ArrayList<String>();

  if (left == n && right == n) {
    results.add("");
  }

  if (left < n) {
    ArrayList<String> subResults = parentheses(n, left + 1, right);
    for (String subResult : subResults) {
      String newResult = "(" + subResult;
      results.add(newResult);
    }
  }

  if (left > right) {
    ArrayList<String> oldResults = parentheses(n, left, right + 1);
    for (String oldResult : oldResults) {
      String newResult = ")" + oldResult;
      results.add(newResult);
    }
  }

  return results;
}

At the end, invoke the recursive function with:

parentheses(n, 0, 0);

Answer 4

Here's a recursive generator that yields all valid solutions. Unlike the other answers, this one never calculates duplicated or invalid strings that need to be filtered out. This is pretty much the same algorithm as in this answer to a previous question, though it doesn't need a non-recursive helper function:

def paren(left, right=None):
    if right is None:
        right = left  # allows calls with one argument

    if left == right == 0: # base case
        yield ""

    else:
        if left > 0:
            for p in paren(left-1, right): # first recursion
                yield "("+p

        if right > left:
            for p in paren(left, right-1): # second recursion
                yield ")"+p

Answer 5

Using recursion, and much for efficient than itertools.permutations:

def paren(n):
    ps = set(['(' * n + ')' * n])
    for i in range(1, n):
        for a in paren(i):
            for b in paren(n-i):
                ps.add(a + b)
    return ps

Because of the repeated recursion, it can also be made more efficient by using functools.lru_cache.

Or, with built-in memoization,

def paren(n, known={}):
    if n in known:
        return known[n]
    ps = set(['(' * n + ')' * n])
    for i in range(1, n):
        for f in paren(i, known):
            for s in paren(n-i, known):
                ps.add(f + s)
    known[n] = ps
    return ps

Answer 6

It seems that the task boils down to generating all possible trees with N+1 nodes. Let's assume another pair of parens around the whole string, then for N=3 all possible trees will be

  o
  |
  o         ((()))
  |
  o
  |
  o

  o
 / \        (())()
o   o
|
o

  o
 / \
o   o       ()(())
    |
    o

  o         ()()()
 /|\
o o o

I can't provide you with any code right now (hence CW), but refer to this paper - it seems to deal with this problem exactly.

Answer 7

If it doesn't have to be done using recursion, this seems to work:

from itertools import permutations

def valid(test):
  open, close = 0, 0
  for c in test:
    if c == '(':
      open += 1
    elif c == ')':
      close += 1
      if close > open:
        return False
  return True

def paren(n):
  perms = set(''.join(p) for p in permutations('(' * n + ')' * n))
  return [s for s in perms if valid(s)]