Author |
Topic: print balanced braces (Read 2396 times) |
|
acumen
Newbie
 
Posts: 13
|
 |
print balanced braces
« on: Jun 9th, 2006, 4:42am » |
 Quote  Modify
|
Given a number n, print all possible combinations of n pairs of braces that are balanced
for example,
n = 2
()()
(())
for n = 3
()()()
(())()
()(())
((()))
(()())
as per what i analysed the number of such combinations is a catalan number (2n n)/n+1
I have even written a program for this, but it has some problem..
can some one just write a code for this?
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: print balanced braces
« Reply #1 on: Jun 9th, 2006, 5:58am » |
Quote Modify
|
Hmm, the number of combinations seems to grow rather quickly with n. 
First off, a procedure just to count them:
Code:int countBraces(int n) {
if (n == 0) return 1;
int sum = 0;
for(int i = 1; i <= n; i++) {
sum += countBraces(i - 1) * countBraces(n - i);
}
return sum;
} |
|
Now, (untested!) (Java) code to print them all
Code:class BracePrinter {
int n, i;
BracePrinter(int N) {
this.n = N;
if (N == 0) { this.i = -1; } else { this.i = 0; }
}
boolean next() { return ++this.i <= this.n; }
void print() {
if (this.n == 0) return;
BracePrinter inside = new BracePrinter(this.i - 1);
while (inside.next()) {
BracePrinter outside = new BracePrinter(this.n - this.i);
while (outside.next()) {
System.out.print("(");
inside.print();
System.out.print(")");
outside.print();
}
}
}
}
void printBraces(int n) {
BracePrinter p = new BracePrinter(n);
while (p.next()) {
p.print();
System.out.println("");
}
} |
|
[edit]fixed missing increment[/edit]
--SMQ
|
| « Last Edit: Jun 9th, 2006, 6:56am by SMQ » |
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: print balanced braces
« Reply #2 on: Jun 9th, 2006, 6:09am » |
Quote Modify
|
on Jun 9th, 2006, 5:58am, SMQ wrote:
Now, (untested!) (Java) code to print them all
|
|
Don't you need to increment i somewhere?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: print balanced braces
« Reply #3 on: Jun 9th, 2006, 6:58am » |
Quote Modify
|
on Jun 9th, 2006, 6:09am, Grimbal wrote:| Don't you need to increment i somewhere? |
|
Erm, yeah, in next().  Fixed now.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: print balanced braces
« Reply #4 on: Jun 9th, 2006, 9:24am » |
Quote Modify
|
fixed? hum...
Well, I fixed it for you.
Code:
package test;
public class BracketIterator implements Runnable
{
private int n;
private String next;
private boolean done;
private Thread backoffice;
public BracketIterator(int n)
{
this.n = n;
next = null;
done = false;
backoffice = new Thread(this);
backoffice.start();
}
public synchronized boolean hasNext()
{
while( next==null && !done ){
try {
wait();
} catch( InterruptedException ex ){
return false;
}
}
return !done;
}
public synchronized String next()
{
while( next==null && !done ){
try {
wait();
} catch( InterruptedException ex ){
return null;
}
}
String ret = next;
next = null;
notifyAll();
return ret;
}
synchronized void yield(String value)
{
while( next!=null && !done ){
try {
wait();
} catch( InterruptedException ex ){
return;
}
}
if( !done ){
next = value;
done = (next == null);
notifyAll();
}
}
public void run()
{
if( n<= 0 ){
yield("");
} else {
for( int i=1 ; i<=n ; i++ ){
BracketIterator inside = new BracketIterator(i-1);
while( inside.hasNext() ){
String prefix = "(" + inside.next() + ")";
BracketIterator outside = new BracketIterator(n-i);
while( outside.hasNext() ){
yield(prefix + outside.next());
}
}
}
}
yield(null);
}
static public void main(String[] arg)
{
BracketIterator it;
for( int n=0 ; n<=4 ; n++ ){
System.out.println("--- " + n);
it = new BracketIterator(n);
while( it.hasNext() ){
System.out.println(it.next());
}
}
System.out.println("---");
}
}
|
|
|
| « Last Edit: Jun 9th, 2006, 9:28am by Grimbal » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: print balanced braces
« Reply #5 on: Jun 9th, 2006, 9:38am » |
Quote Modify
|
on Jun 9th, 2006, 9:24am, Grimbal wrote:
Er, in the sense that it does what I was thinking, yes. In the sense of solving the problem, no, not so much.
How about this version (which I've actually tested...)
Code:class BracePrinter {
int n, i;
BracePrinter inside, outside;
BracePrinter(int N) {
this.n = N;
this.i = 1;
if (this.i <= this.n) {
this.inside = new BracePrinter(this.i - 1);
this.outside = new BracePrinter(this.n - this.i);
} else {
this.inside = this.outside = null;
}
}
boolean next() {
if (this.i > this.n) return false;
if (this.outside.next()) return true;
if (this.inside.next()) return true;
if (++this.i > this.n) return false;
this.inside = new BracePrinter(this.i - 1);
this.outside = new BracePrinter(this.n - this.i);
return true;
}
void print() {
if (inside == null || outside == null) return;
System.out.print("(");
inside.print();
System.out.print(")");
outside.print();
}
}
void printBraces(int n) {
BracePrinter p = new BracePrinter(n);
do {
p.print();
System.out.println("");
} while (p.next());
} |
|
Quote:| Well, I fixed it for you. |
|
 Oh my! Well, I recognize the variable names "inside" and "outside" Nice approach!
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: print balanced braces
« Reply #6 on: Jun 9th, 2006, 9:52am » |
Quote Modify
|
I saw the idea of the main loop and tried to make it work (i.e. define an iterator as a procedure). I think C# has a language feature for that which would save the whole thread synchronization thing.
This being said, I think you still don't print all combinations...
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: print balanced braces
« Reply #7 on: Jun 9th, 2006, 11:33am » |
Quote Modify
|
on Jun 9th, 2006, 9:52am, Grimbal wrote:| This being said, I think you still don't print all combinations... |
|
Ahh, dang, you're right again. I missed one line--in next() it should be:
Code:...
if (this.outside.next()) return true;
this.outside = new BracePrinter(this.n - this.i);
if (this.inside.next()) return true;
... |
|
But how about this much simpler approach:
Code:void printSequence(String prefix, int N, int O) {
if (O > 0) printSequence(prefix + ')', N, O - 1);
if (N > 0) printSequence(prefix + '(', N - 1, O + 1);
if (N == 0 && O == 0) System.out.println(prefix);
}
void printBraces(int n) { printSequence("", n, 0); } |
|
Where for printSequence, prefix is the string built so far, N is the number of open-braces still available to use, and O is the number of currently open braces (the number of close-braces needed).
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: print balanced braces
« Reply #8 on: Jun 11th, 2006, 10:55am » |
Quote Modify
|
Also, look at Fig. 3 in the following article.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: print balanced braces
« Reply #9 on: Jun 11th, 2006, 3:17pm » |
Quote Modify
|
on Jun 9th, 2006, 11:33am, SMQ wrote:
But how about this much simpler approach:
Code:void printSequence(String prefix, int N, int O) {
if (O > 0) printSequence(prefix + ')', N, O - 1);
if (N > 0) printSequence(prefix + '(', N - 1, O + 1);
if (N == 0 && O == 0) System.out.println(prefix);
}
void printBraces(int n) { printSequence("", n, 0); } |
|
|
|
I'll tell you what: This is probably more elegant and efficient than my multi-threaded solution. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print