techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Parentheses

Given n pairs of parentheses. Write a program to print out all valid configrations.

For example n=2, ()(), (()) are valid, but ))((, ())( are not.
JK
Thursday, January 11, 2007
 
 
My first response is to use dynamic programming, at least DP can find out the total number of valid parenthesization. Printing out the solutions would then bowl down to backtracking. I will come back with code later.
Verdi
Thursday, January 11, 2007
 
 
My idea is to use Stack, need to perform push and pop operations with corresponding ( and ).
Nagesh Ayyagari
Friday, January 12, 2007
 
 
can anyone think of this on the lines of using DFS..

lets say for n = 3, we createa a graph with 3 nodes. The start and finish times of DFS on a tree satisfies the parenthesis theorem. Now what could be the different ways of placing edges between the nodes...?
Varun Send private email
Friday, January 12, 2007
 
 
I agree with Nagesh. Stack is good data structure here.

I think we need recursion to exhaust all possibilities.
Yao
Friday, January 12, 2007
 
 
Here is an iterative solution:

void parens(int pairs)
{
    int i, j, s, n = 2*(pairs - 1);

    for (i = 0; i < 1 << n; i++) {
        for (s = 1, j = 0; (j < n) && (s >= 0) && (s <= pairs); j++)
            s += ((i >> j) & 1) ? 1 : -1;
        if ((j != n) || (s != 1))
            continue;
        putchar('(');
        for (j = 0; j < n; j++)
            ((i >> j) & 1) ? putchar('(') : putchar(')');
        printf(")\n");
    }
}
Sajid
Friday, January 12, 2007
 
 
Sajid, some comments please?

It seems to me you use a bit pattern to control the generation.
JK
Friday, January 12, 2007
 
 
With a reasonable string class...iteratively...

void pairs(int num)
{
 pairs(0, num, 0, "");
}

void pairs(int num_L_placed, int num_L_to_place, int num_R_placed, string state)
{
 if(num_L_to_place == 0 && num_R_to_place == 0)
 {
  printf(state);
  return;
 }
 if(num_L_to_place > 0)
 {
  pairs(num_L_placed + 1, num_L_to_place - 1, num_R_placed, state + "(")
 }
 if(num_R_placed < num_L_placed)
 {
  pairs(num_L_placed, num_L_to_place, num_R_placed + 1, state + ")")
 }
}
MikeD Send private email
Friday, January 12, 2007
 
 
JK, you're right.

A bit pattern like:

    10101100

Can be intepreted as:

    ()()(())

The function cycles through all bit patterns of the appropriate length and eliminates those that fail the three tests described below.

The tests depend on calculating the sums of the bit patterns, with 0 being replaced by -1.

    e.g. sum(1100) = 1 + 1 - 1 - 1 = 0

Here are the tests:

(1) sum(bitpattern) = 0

Here is an example which fails:

    sum(1110) = 1 + 1 + 1 - 1 = 2

(2) All partial sums must be >= 0.

Here is an example which fails:

    bitpattern = 1001

    sum(1) = 1

    sum(10) = 1 - 1 = 0

    sum(100) = 1 - 1 - 1 = -1 *

    sum(1001) = 1 - 1 - 1 + 1 = 0

(3) All partial sums must <= pairs/2

Here is an exmple which fails:

    bitpattern = 1110

    sum(1) = 1

    sum(11) = 1 + 1 = 2

    sum(111) 1 + 1 + 1 = 3 *

    sum(111) = 1 + 1 + 1 - 1 = 2

To make the code a little bit more efficient, we ignore the first and last parantheses, because the first will always be '(' and the last will always be ')'.
Sajid
Friday, January 12, 2007
 
 
Bravo, Sajid!

By the way, the total number of valid configurations of n pair is the nth Catalan number C(n).
J.Guo Send private email
Friday, January 12, 2007
 
 
Sajid, do you know the proportion of binary values that will work for each length of the binary string?

Unfortunately I'm not at work and don't have MS-Dev on this computer else I'd tell you for certain but I think that with a length of 2 (4 brackets totals) 5 / 16 work. With a length of 3 (6 brackets total) 15 / 64 work. I didn't triple check this but I'm wondering whether it's a downward slope and the algorithm will become sub-optimal for large values of N.
MikeD Send private email
Saturday, January 13, 2007
 
 
Mike, you're right, the proportion is:

    (2n)!/(n + 1)!n!4^n

Which tends to 0 as n gets larger.

So the algorithm isn't anywhere near optimal.
Sajid
Saturday, January 13, 2007
 
 
Here's a very brief description of a strategy I think will work but can't quite get my head around codifying.

Using the binary representation method as stated in previous posts, for n pairs produce a binary representation with n 1's followed by n 0's.
i.e. for 4 brackets, start with 11110000
Calling this array of bits B[] for simplicity, we start off with two iterators, x = B[1] y = B[n-2] (because you'll never want to swap the leading/trailing values as Sajid pointed out). You then iterate the index forwards/backwards respectively, swapping bits and storing the swaps you've made on a stack (to avoid recursion, though this could be done recursively as well). You keep record of the number of swaps and only make a new swap if the number of swaps is greater than floor(x/2). x would be iterated in an outer loop, y in an inner loop. Every time x or y pass the midpoint of B then you undo the previous swap, pop the top of the stack and move x and y back to the position of that swap, then continue iterating through with the loops. You finish when x passes the midpoint and the stack is empty.

Sorry this is vague, but I think it should produce all the valid permutations. If I have time later I'll try and write it out as code.
MikeD Send private email
Saturday, January 13, 2007
 
 
Sounds complicated :-)
Sajid
Saturday, January 13, 2007
 
 
By the way, after thinking about this some more, I've found a recursive solution which is optimal:

void parens(int pairs)
{
    char output[2*pairs];

    output[0] = '(';
    output[2*pairs - 1] = ')';

    foo(output, 1, 1, pairs); 
}

void foo(char output[], int index, int sum, int pairs)
{
    int i;

    if (index == 2*pairs - 1) {
        if (sum == 1) {
            for (i = 0; i < 2*pairs; i++)
                putchar(output[i]);
            }
            return;
        }

        if (sum + 1 <= pairs) {
            output[index] = '(';
            foo(output, index + 1, sum + 1, pairs);
        }

        if (sum - 1 >= 0) {
            output[index] = ')';
            foo(output, index + 1, sum - 1, pairs);       
        }

        return;
}

It uses the same set of ideas I described earlier.
Sajid
Saturday, January 13, 2007
 
 
It's just occurred to me that although my latest solution is good, it is not optimal.

It discards some illegitimate configurations right at the end with the 'if (sum == 1)' statement:

    if (index == 2*pairs - 1) {
        if (sum == 1) {
            for (i = 0; i < 2*pairs; i++)
                putchar(output[i]);
            }
        return;
    }

A truly optimal solution would only build legitimate configurations.
Sajid
Saturday, January 13, 2007
 
 
I've finally grokked this problem.

The final solution is simple and truly optimal.

Simply build configurations from left to right using an equal number of opening and closing parantheses.

At each stage, make sure that the number of closing parantheses used does not exceed the number of openening parantheses used.

Here's the code:

void parens(int pairs)
{
    char output[2*pairs];

    output[0] = '(';
    output[1] = ')';

    foo(output, 1, pairs - 1, pairs, pairs); 
}

void foo(char output[], int index, int open, int close, int pairs)
{
    int i;
   
    if (index == 2*pairs) {
        for (i = 0; i < 2*pairs; i++)
            putchar(output[i]);
        putchar('\n');
        return;
    }

    if (open) {
        output[index] = '(';
        foo(output, index + 1, open - 1, close, pairs);
    }

    if (close && (pairs - close + 1 <= pairs - open)) {
        output[index] = ')';
        foo(output, index + 1, open, close - 1, pairs);       
    }

    return;
}
Sajid
Saturday, January 13, 2007
 
 
The fourth line should read:

    output[2*pairs - 1] = ')';

Not:

    output[1] = ')';
Sajid
Saturday, January 13, 2007
 
 
I'll try to write down my solution without code (and apologise in advance if it was already coded here).

1. We start with all the '1' aka ')' at the right position:
  0000011111
2. To get next combination - move leftmost '1' one position to the left
3. Do it till it reaches second position:
  0100001111
4. Now move second '1' to the left and shift the first '1' all the way back to the right:
  0000110111
5. Get back to step 2
6. Once we repeat step 4 - make sure second '1' won't get past 4th position:
  0101000111
7. Proceed by shifting 3rd '1' to the left and 1st and 2nd back to the right:
  0000111011
8. Repeat previous steps till no more moves are allowed:
  0101010101

This is the idea, implementation can be recursive or interactive.
For instance, let's say we have some valid combination in position[N] and want to get the next one by these rules:

bool isLastCombination = true;

for(int i=0; i<N-1; i++)
{
  if(position[i] > 2*i+1)
  {
    // shift element #i to the left, shift all those before #i to the right
    //
    for(j=0; j<=i; j++) position[j] = position[i] - (i-j) - 1;
    isLastCombination = false;
    continue;
  }
}
DK
Sunday, January 14, 2007
 
 
urgh, sorry, there should be "break", instead of "continue".
DK
Sunday, January 14, 2007
 
 
A recursive solution with a globval array for putting the strings would be

foo(n)
{
  //IF n==1, generate string '()' and put it in the global //array and increment index count by 2. If index is in last //psition print the global array decrement index by 2 and //return

  //First generate string with all left brace preceding all //right braces like '()', '(())', '((()))' and put it in the //global array and increment index count by 2n. If index is in last position print the global array decrement index by 2n and return

  for(int i=1; i<n ;i++)
  {
    foo(i)
    foo(n-i);
  }
}


For taking care of duplicate position, the n's can be multipied with their positions and the index for the sum array can be marked.


For example for n=2,

 it will be first

 (()) printed with sum 0*1 + 2*2 = 4 marked.

  next will be foo(1), foo(1)

  which will print ()()

  with sum 1*1 + 1*2 = 3 marked

 
For n=3,

  ((())) ,  9 marked.
 
  next foo(1) foo(2)

  which will generate

  ()(())  1*1 + 0*2 + 2*3 = 7 marked
  ()()()  6 marked
 
  next foo(2) foo(1)

  (())()
  ()()() will give 6 already marked so dont print
   
  thats all and so on
shawshank
Sunday, February 11, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz