Well formed parenthesis pairs

A friend came to me recently and posed an interesting problem. Given a number n how many valid balanced open/close parenthesis combinations are there?

Examples:

n == 4

1. ()()
2. (())

n == 6

1. ()()()
2. (()())
3. ()(())
4. (())()
5. ((()))

His solution:

• The number n must be even
• Treat '(' as 1
• Treat ')' as 0
• The minimal value will be "10" n/2 times. ie 101010
• The maximum value will be "1" n/2 times followed by "0" n/2 times. ie 111000
• The odd parity must be n/2
• The even parity must be n/2
• The combinations must be well formed ie (()) and not ))((

The algorithm to solve the problem went like this: Say n is 8, loop from 10101010 to 11110000 by 2's (to exclude odd numbers), make sure that the even parity equals n/2 and that the odd parity equals n/2. For each number loop over the bits and add +1 for 1 and subtract -1 for 0. Throw out any number that goes below 0 at any point.

This algorithm will get you to the correct solution but the solution involved heuristics and considered some invalid combinations. I was sure that there was a way to solve this problem without considering any invalid combinations and I was right. Here is my solution (with an implementation in ruby):

Note: I would not be surprised if there is a mathematically more efficient way to solve this problem, but this is what I came up with.

1. Create a grid of all the possibilities.
2. Create a directed graph.
3. Walk the graph from the end to the beginning.

I am including four figures now that I will reference below.

Create a grid of all the possibilities. Thinking in terms of a turn based stack, the blue squares in figure A can be ruled out as invalid.

Create a directed graph. Again thinking in terms of our stack, there are only two possible operations, push and pop. So as we move from turn 1 to turn 2 we must go either up and to the right OR down and to the right. I also consider the two possible incoming points because my directed graph is bi-directional (think in terms of a doubly linked list). So for the point (0,0) we can see the four possibilities in figure B. They are (-1,1), (-1,-1), (1,-1) and (1,1). Of these four only the point (1,1) falls in a yellow square and is therefore "valid". We then move on to this point and repeat the process until we end up at point (n,0) which is always our last point. At this point our data structure looks like diagram C.

Finally, we have to walk our structure to determine all the valid combinations. My first thought was to walk from the point (0,0) to (n,0) but I ended up walking from the end to the beginning! (Either way works, but I found the code easier to write going in the opposite direction). Using the labels from diagram D we see the valid combinations are:

• J I H F D B A
• J I H E D B A
• J I H E C B A
• J I G E D B A
• J I G E C B A

Note 1: My algorithm to walk the data structure is not perfect. The algorithm is recursive but not tail recursive so for very large data structures memory could be an issue. The maximum number of stack frames will be equal to n. Note 2: The algorithm takes a long time for large numbers because there are many, many valid combinations to consider. In real life, this algorithm would have to be modified to parallelize the effort across processors/machines.

And finally, the ruby code!

class DirectedBinaryGraphNode
  attr_accessor :last_lower, :last_higher, :next_lower, :next_higher, :x, :y
  def initialize(x,y)
    @x = x; @y = y
  end
  def to_s()
    "#{x}, #{y}"
  end
end

def validate_node(n,index)
  x = index[0]; y = index[1]
  width = x >= 0 and x <= n
  vertical = (x < (n/2)) ? x : (n-x)
  height = (y >= 0 and y <= vertical)
  x <= n and width and height
end

def ensure_node(index,n) 
  if ( @nodes[index] ) then
    node = @nodes[index]
  else
    node = DirectedBinaryGraphNode.new(index[0],index[1])
    @nodes[index] = node
    create_node(n,node)
  end
  node
end

def create_node(n,node)
  puts "creating node #{node}"
  last_lower = [node.x-1,node.y-1]
  last_higher = [node.x-1,node.y+1]
  node.last_lower = ensure_node(last_lower,n) if validate_node(n,last_lower)
  node.last_higher = ensure_node(last_higher,n) if validate_node(n,last_higher)
  next_lower = [node.x+1,node.y-1]
  next_higher = [node.x+1,node.y+1]
  node.next_lower = ensure_node(next_lower,n) if validate_node(n,next_lower)
  node.next_higher = ensure_node(next_higher,n) if validate_node(n,next_higher)
end

def create_data_structure(n)  
  @nodes[[0,0]] = DirectedBinaryGraphNode.new(0,0) 
  create_node(n,@nodes[[0,0]]) 
end

def walk_data_structure(str,last)
  if ( last.last_lower) then
    walk_data_structure("(" + str,last.last_lower)
  end
  if ( last.last_higher) then
    walk_data_structure(")" + str,last.last_higher) 
  end 
  unless last.last_lower or last.last_higher then
    @cnt = @cnt + 1
    puts "Valid combo: #{str}"
  end
end

n = ARGV[0].to_i
unless ( n % 2 == 0 ) then
  puts "invalid parameter #{n} [it must be even]"
  exit -1
end
@nodes = {}; @cnt = 0
create_data_structure(n)
walk_data_structure("",@nodes[[n,0]])
puts "Total number: #{@cnt}"