Home > Applied Algorithms, Permutations > Valid Parentheses Combinations

Valid Parentheses Combinations

Problem Statement: You are given a number of pairs of parentheses. You are supposed to print all valid combinations using all these parentheses.

This question is only an example of questions where you are supposed to find all the permutations of a set of elements. I am using this question to demonstrate the method to perform all such permutations.

So how do you go about finding all permutations. Here is a great method to do so. Start with a single parentheses. Now start inserting the remaining parentheses at all the possible locations. Here is how it goes if we are given 2 pairs of parentheses.

(,),(,)    //available elements

Now constructing all possibilites:

( //start — 0

()  //inserting ) to the right in 0 — 1

)(  //inserting ) to the left in 0 — 2

()( //inserting ( to the right in 1 or left of 2 — 3

(() //inserting ( either in the middle or left of 1 — 4

)(( //inserting ( in the middle of 2 — 5

()(), ())( , )()( //inserting ) at different places in 3 — 6

(()) , ()() , )(() //inserting ) at different places in 4 — 7

)(() , )()( , ))(( //inserting ) at different places in 5 — 8

Now all you need to do is find the valid combinations from those generated in 6, 7 and 8. Handy technique, right?! 🙂

PS: Leave a comment if you don’t know how to check validity of parentheses combinations and I’ll write a post on that as well.

 

Advertisements
  1. November 4, 2011 at 4:19 pm

    Being a “compiler guy”, I’d take a different approach.

    First observe is that the list of perfectly balanced paren-expressions
    is completely described by the context-free grammar:

    B = E | B ‘(‘ B ‘)’ /* E is the empty string. */

    This gives a nice recursive relation: for generating all the
    paren-expressions of length N, first generate all the
    paren-expressions of length X and Y, such that X + Y == (N – 2).
    So, for N = 6, you generate the following sets:

    X = 0 (only the empty string), Y = 4 (some set of strings) — (A)
    X = 2 (paren-expressions always have an even length), Y = 2 — (B)
    X = 4, Y = 0 — (C)

    Then iterate through this set S = { A, B, C }. Each element of this set
    S is itself a pair of set of strings. For each pair we generate all
    the strings possible by taking `x` from the first set in the pair and
    `y` from the second, and adding `x` + “(” + `y` + “)” to our solution
    set (the one we’re trying to calculate). This should result in the
    solution set containing exactly all the paren-expressions of length N.

    This is one of those algorithms which are harder to write down than to
    intuitively understand. 🙂

    For completeness, here is a (very slow) implementation in Haskell:

    b n = if n == 0 then [“”] — One empty string
    else
    let limit = n / 2
    stringList = [(b $ 2 * x, b $ 2 * y)
    | x <- [0..limit – 1],
    y [m ++ “(” ++ n ++ “)” |
    m <- x, n <- y]) stringList

    PS: Awesome work regularly updating the blog. Most people lose motivation. 🙂

    • November 4, 2011 at 5:09 pm

      Hah! Never thought of it that way. Nice 🙂 But won’t that be slower? Just wondering.

      And thanks, plan to continue with the regular updates. 🙂

  2. November 4, 2011 at 4:20 pm

    Of course, since you’re given “The number of parens is X”, you’ll have the feed “The length of the paren-expr is 2 * X” to the above algorithm.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: