6
\$\begingroup\$

Question goes like this :

input: 1
output:
{}

input: 2
output:
{}{}
{{}}

input: 3
output:
{}{}{}
{{}}{}
{}{{}}

This is my program :

public class PrintBraces {
    int n;
    char []braces;

    void readData()
    {
        java.util.Scanner scn=new java.util.Scanner(System.in);
        System.out.print("Please enter the value of n : ");
        n=scn.nextInt();
    }

    void manipulate()
    {
        braces=new char[n*2];

        for(int i=0;i<2*n;i+=2)
        {
            braces[i]='{';
            braces[i+1]='}';
        }

        for(int i=0;i<n;i++)
        {
            int oddNo=2*i-1;
            if(oddNo>0)
            {
                char temp=braces[oddNo];
                braces[oddNo]=braces[oddNo+1];
                braces[oddNo+1]=temp;

                print();

                temp=braces[oddNo];
                braces[oddNo]=braces[oddNo+1];
                braces[oddNo+1]=temp;
            }
            else
            {
                print();
            }
        }
    }

    void print()
    {
        for(int i=0;i<2*n;i++)
        {
            System.out.print(braces[i]);
        }
        System.out.println();
    }
}

class PrintMain
{
    public static void main(String args[])
    {
        PrintBraces pb=new PrintBraces();
        pb.readData();
        pb.manipulate();
    }
}

As expected, I get the correct answer.

I have solved it but I think it isn't efficient enough. Can anyone optimise it? And I would love to see any other alternative approaches for the same problem. May be a recursive one? Also, I am open to any suggestions for improving my programming style. Any good practices that I may be violating in my code?

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Why doesn’t the output for 3 contain {{{}}}? Are only two levels of nesting allowed? \$\endgroup\$ Jun 20, 2012 at 11:42

3 Answers 3

6
\$\begingroup\$
public class Solution{

    public static void par(int n, int open, int closed, String str) {

        if (closed == n) {
            System.out.println(str);
            return;
        }

        if (open < n) {
            par(n, open+1, closed, str + "{");
        }

        if (closed < open) {
            par(n, open, closed+1, str + "}");
        }
    }

    public static void main(String[] args) throws Exception {

        par(Integer.parseInt(args[0]), 0, 0, "");

    }
}

Output fot the testcase 3:

{{{}}}
{{}{}}
{{}}{}
{}{{}}
{}{}{}

If you need additional speed - you should use the buffered output. Something like this:

import java.io.*;
import java.util.*;

public class Solution{

    static BufferedWriter out; 

    public static void par(int n, int open, int closed, String str)  throws IOException {

        if (closed == n) {
            out.write(str + "\n");
            return;
        }

        if (open < n) {
            par(n, open+1, closed, str + "{");
        }

        if (closed < open) {
            par(n, open, closed+1, str + "}");
        }
    }

    public static void main(String[] args) throws IOException  {
        out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 4096);
        par(Integer.parseInt(args[0]), 0, 0, "");
        out.flush();
    }
}

For example the first version for 13 takes ~ 17 seconds:

timethis %JAVA_HOME%/bin/java -server Solution 13 >13.txt

the buffered output version ~ 0.4 second!

PS. Interesting that jdk1.7.0_04 ~ 5 times faster than that c version:

#include<stdio.h>
#include<string.h>

unsigned long pairs_count;
unsigned long *brackets;
unsigned long found = 0;

void print_result()
{
    unsigned long i, j;

    for (i = 0; i < pairs_count; i++) {
    printf("(");

    for (j = 0; j < pairs_count; j++)
        if (brackets[j] == i)
        printf(")");
    }

    printf("n");
    found++;
}

void step(unsigned long start_val, unsigned long pos)
{
    unsigned long k, i;

    if (start_val > pos)
    k = start_val;
    else
    k = pos;

    for (i = k; i < pairs_count; i++) {
    brackets[pos] = i;

    if (pos == pairs_count - 1)
        print_result();
    else
        step(i, pos + 1);
    }
}

int main()
{

    scanf("%d", &pairs_count);

    brackets = new unsigned long[pairs_count];

    if (!brackets) {
    printf("Unsufficient memory.n");
    return (0);
    }

    step(0, 0);

    delete brackets;

    printf("Found: %d.n", found);

    return (0);
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can you guide me through the code? I personally find it difficult to grasp recursive algos and I need to get good at it. So can you suggest me a good source for mastering recursive algos? \$\endgroup\$
    – Kameron
    Jun 20, 2012 at 12:10
  • \$\begingroup\$ Nice, very clean implementation (but an explanation would be in order). Now, how to rewrite it using dynamic programming? \$\endgroup\$ Jun 20, 2012 at 12:18
  • \$\begingroup\$ +1 - String concatenation isn't the most efficient thing around. Of course, passing StringBuilder or StringBuffer wouldn't help much, because you'd need to copy them at each level - This might warrant a custom CharSequence or something (as linked list? Although String may have this behavior by default...). Code is a lot cleaner than what I was initially coming up with, although a bit of an explanation would be helpful. \$\endgroup\$ Jun 20, 2012 at 22:49
  • \$\begingroup\$ The algorithm is very simple: 1. The first brace is { 2. The last brace is } 3. On the same level } goes right after { 4. The amount of { braces is equal to amount of the } braces. 5. Recursion does the rest job. \$\endgroup\$
    – cat_baxter
    Jun 21, 2012 at 8:25
4
\$\begingroup\$

The given problem can be attempted in a slightly different manner. You can see that the pairing corresponds to binary digits with { standing for 1s and } standing for 0s.

For e.g the pairing with the maximum value for say 4 {}'s is 11110000. So all we have to do is to generate every number from 1 to 11110000 and strike out all numbers that do not conform to our requirement - that is, at no point while counting the digits from left in a number, can the number of 1s be lesser than the number of 0s, and also that the total count of 1s and 0s must be equal.

A few optimizations can be done, For e.g, all odd numbers can be eliminated. And the total number of digits have to be even, etc.

If the number of braces are n, then the algorithm is of O(2^n) complexity. So it is not an efficient algorithm. I wonder what the complexity of your algorithm is, and how you can show that your algorithm is indeed correct.

For additional ideas ref: catalan numbers.

\$\endgroup\$
1
  • \$\begingroup\$ Excellent idea ... post some code. I am all for non-recursive solutions when they exist. \$\endgroup\$ Jun 21, 2012 at 0:57
0
\$\begingroup\$

Here's my effort. It's a little like @cat_baxter's one. The point I am making here is that if you add loads of comments to your code, sometimes just the effort of doing so makes the code better.

I think this is optimal, i.e. it never starts growing a sequence towards an invalid position, but I don't fancy trying to prove that.

public class PrintBraces {
  public static void main(String[] args) {
    // Do a number of them.
    for (int i = 1; i < 10; i++) {
      System.out.println("Print Braces: " + i);
      printBraces(i);
    }
  }

  private static void printBraces(int n) {
    // There will always be n*2 characters in the brace array.
    char[] braces = new char[n * 2];
    // Start at position 0 with 0 opened.
    printBraces(braces, 0, 0);
  }

  private static void printBraces(char[] braces, int opened, int offset) {
    // How much space is left in the array?
    int space = braces.length - offset;
    // Are we at the end of the array?
    if (space > 0) {
      // We can open or close so try both.
      // We can only open if there is enough room to close all opened and at least one more.
      if (space > opened) {
        printBraces(braces, opened, offset, true);
      }
      // We can only close if we are opened more than once.
      if (opened > 0) {
        printBraces(braces, opened, offset, false);
      }
    } else {
      // Array is full! Is it legal?
      if (opened == 0) {
        System.out.println(braces);
      } else {
        // Here just for my sanity. Code never gets here - proving we are correct.
        System.out.println("?-" + braces);
      }
    }
  }

  private static void printBraces(char[] braces, int opened, int offset, boolean open) {
    // Add that kind of brace and recurse.
    braces[offset] = open ? '{' : '}';
    printBraces(braces, opened + (open ? 1 : -1), offset + 1);
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.