Algorithm to print all valid combations of n pairs of parenthesis

Question

I'm working on the problem stated in the question statement. I know my solution is correct (ran the program) but I'm curious as to whether or not I'm analyzing my code (below) correctly.

def parens(num)
  return ["()"] if num == 1
  paren_arr = []
  parens(num-1).each do |paren| 
    paren_arr << paren + "()" unless "()#{paren}" == "#{paren}()"
    paren_arr << "()#{paren}"
    paren_arr << "(#{paren})"
  end
  paren_arr
end

parens(3), as an example, will output the following:

["()()()", "(()())", "(())()", "()(())", "((()))"]

Here's my analysis: Every f(n) value is roughly 3 times as many elements as f(n-1). So:

f(n) = 3 * f(n-1) = 3 * 3 * f(n-2) ~ (3^n) time cost. By a similar analysis, the stack will be occupied by f(1)..f(n) and so the space complexity should be 3^n.

I'm not sure if this analysis for either time or space is correct. On the one hand, the stack only holds n function calls, but each of these calls returns an array ~3 times as big as the call before it. Does this factor into space cost? And is my time analysis correct?

Answer 1

As others have mentioned, your solution is not correct.

My favourite solution to this problem generates all the valid combinations by repeatedly incrementing the current string to the lexically next valid combination.

"Lexically next" breaks down into a few rules that make it pretty easy:

• The first difference in the string changes a '(' to a ')'. Otherwise the next string would be lexically before the current one.

• The first difference is as far to the right as possible. Otherwise there would be smaller increments.

• The part after the first difference is lexically minimal, again because otherwise there would be smaller increments. In this case that means that all the '('s come before all the ')'.

So all you have to do is find the rightmost '(' that can be changed to a ')', flip it, and then append the correct number of '('s and ')'s.

I don't know Ruby, but in Python it looks like this:

current="(((())))"
while True:
    print(current)
    opens=0
    closes=0
    pos=0
    for i in range(len(current)-1,-1,-1):
        if current[i]==')':
            closes+=1
        else:
            opens+=1
            if closes > opens:
                pos=i
                break
    if pos<1:
        break
    current = current[:pos]+ ")" + "("*opens + ")"*(closes-1)

Output:

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

Solutions like this turn out to be easy and fast for many types of "generate all the combinations" problems.

Answer 2

Recursive reasoning makes a simple solution. If the number of left parens remaining to emit is positive, emit one and recur. If the number of right parens remaining to emit is greater than the number of left, emit and recur. The base case is when all parens, both left and right, have been emitted. Print.

def parens(l, r = l, s = "")
  if l > 0 then parens(l - 1, r, s + "(") end
  if r > l then parens(l, r - 1, s + ")") end
  if l + r == 0 then print "#{s}\n" end
end

As others have said, the Catalan numbers give the number of strings that will be printed.

While this Ruby implementation doesn't achieve it, a lower level language (like C) would make it easy to use a single string buffer: O(n) space. Due to substring copies, this one is O(n^2). But since the run time and output length are O(n!), O(n) space inefficiency doesn't mean much.

Answer 3

I found Tom Davis' article, "Catalan Numbers," very helpful in explaining one recursive method for defining the Catalan Numbers. I'll try to explain it myself (in part, to see how much of it I've understood) as it may be applied to finding the set of all unique arrangements of N matched parentheses (e.g., 1 (); 2 ()(), (()); etc. ).

For N > 1 let (A)B represent one arrangement of N matched parentheses, where A and B each have only balanced sets of parentheses. Then we know that if A contains k matched sets, B must have the other N - k - 1, where 0 <= k <= N - 1.

In the following example, a dot means the group has zero sets of parentheses:

C_0 => .

C_1 => (.)

To enumerate C_2, we arrange C_1 as AB in all ways and place the second parentheses around A:

. () = AB = C_0C_1 => (.)()

() . = AB = C_1C_0 => (()) .

Now for C_3, we have three partitions for N - 1, each with its own combinations: C_0C_2, C_1C_1, C_2C_0

C_0C_2 = AB = . ()() and . (()) => ()()(), ()(())
C_1C_1 = AB = ()()              => (())()
C_2C_0 = AB = ()() . and (()) . => (()()), ((()))

We can code this method by keeping a set for each N and iterating over the combinations for each partition. We'll keep the individual arrangements as bits: 0 for left and 1 for right (this appears backwards when cast as a binary string).

def catalan
  Enumerator.new do |y|
    # the zero here represents none rather than left
    s = [[0],[2]]
    y << [0]
    y << [2]
    i = 2

    while true
      s[i] = []

      (0..i - 1).each do |k|
        as = s[k]
        bs = s[i - k - 1]

        as.each do |a|
          bs.each do |b|
            if a != 0
               s[i] << ((b << (2*k + 2)) | (1 << (2*k + 1)) | (a << 1)) 
            else
               s[i] << (2 | (b << 2))
            end

          end # bs
        end # as

      end # k

      y.yield(s[i])

      i = i + 1
    end # i

  end # enumerator
end

catalan.take(4) 
# => [[0], [2], [10, 12], [42, 50, 44, 52, 56]]

The yielder is lazy: although the list is infinite, we can generate as little as we like (using .take for example):

catalan.take(4).last.map{|x| x.to_s(2)} 
# => ["101010", "110010", "101100", "110100", "111000"]

The former generation obliges us to keep all previous sets in order to issue the next. Alternatively, we can build a requested set through a more organic type, meandering recursion. This next version yields each arrangement to the block, so we can type:

catalan(4){
  |x| (0..7).reduce(""){
    |y,i| if x[i] == 0 then y + "(" else y + ")" end
  }
}.take(14)

# => ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())",
#     "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()",
#     "()()(())", "()()()()"]

Direct generation:

def catalan(n)
  Enumerator.new do |y|
    s = [[0,0,0]]

    until s.empty?
      left,right,result = s.pop

      if left + right == 2 * n
        y << yield(result)
      end

      if right < left
        s << [left, right + 1, result | 1 << (left + right)]
      end

      if left < n
        s << [left + 1, right, result]
      end
    end

  end
end