#195
Parentheses... Again
 

Difficulty:Medium
Topics:math combinatorics


In a family of languages like Lisp, having balanced parentheses is a defining feature of the language. Luckily, Lisp has almost no syntax, except for these "delimiters" -- and that hardly qualifies as "syntax", at least in any useful computer programming sense.

It is not a difficult exercise to find all the combinations of well-formed parentheses if we only have N pairs to work with. For instance, if we only have 2 pairs, we only have two possible combinations: "()()" and "(())". Any other combination of length 4 is ill-formed. Can you see why?

Generate all possible combinations of well-formed parentheses of length 2n (n pairs of parentheses). For this problem, we only consider '(' and ')', but the answer is similar if you work with only {} or only [].

There is an interesting pattern in the numbers!


test not run
(= [#{""} #{"()"} #{"()()" "(())"}] (map (fn [n] (__ n)) [0 1 2]))
test not run
(= #{"((()))" "()()()" "()(())" "(())()" "(()())"} (__ 3))
test not run
(= 16796 (count (__ 10)))
test not run
(= (nth (sort (filter #(.contains ^String % "(()()()())") (__ 9))) 6) "(((()()()())(())))")
test not run
(= (nth (sort (__ 12)) 5000) "(((((()()()()()))))(()))")


Code which fills in the blank: