Printing braces

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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