## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
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
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 + ")") } }
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
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.
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.
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
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 |

Powered by FogBugz