wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> print balanced braces
        
(Message started by: acumen on Jun 9^th, 2006, 4:42am)

Title: print balanced braces
Post by acumen on Jun 9^th, 2006, 4:42am

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?

Title: Re: print balanced braces
Post by SMQ on Jun 9^th, 2006, 5:58am

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

Title: Re: print balanced braces
Post by Grimbal on Jun 9^th, 2006, 6:09am

on 06/09/06 at 05:58:19, SMQ wrote:

Now, (untested!) (Java) code to print them all

Don't you need to increment i somewhere?

Title: Re: print balanced braces
Post by SMQ on Jun 9^th, 2006, 6:58am

on 06/09/06 at 06:09:30, Grimbal wrote:

Don't you need to increment i somewhere?

Erm, yeah, in next(). :-[ Fixed now.

--SMQ

Title: Re: print balanced braces
Post by Grimbal on Jun 9^th, 2006, 9:24am

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("---");
}
}

Title: Re: print balanced braces
Post by SMQ on Jun 9^th, 2006, 9:38am

on 06/09/06 at 09:24:28, Grimbal wrote:

fixed? hum...

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.

:o Oh my! Well, I recognize the variable names "inside" and "outside" ;) Nice approach!

--SMQ

Title: Re: print balanced braces
Post by Grimbal on Jun 9^th, 2006, 9:52am

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...

Title: Re: print balanced braces
Post by SMQ on Jun 9^th, 2006, 11:33am

on 06/09/06 at 09:52:25, 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

Title: Re: print balanced braces
Post by Barukh on Jun 11^th, 2006, 10:55am

Also, look at Fig. 3 in the following article (http://mjcs.fsktm.um.edu.my/document.aspx?FileName=285.pdf).

Title: Re: print balanced braces
Post by Grimbal on Jun 11^th, 2006, 3:17pm

on 06/09/06 at 11:33:06, SMQ wrote:

But how about this much simpler approach:

Code:

I'll tell you what: This is probably more elegant and efficient than my multi-threaded solution. ;D