Counting the number of valid bracket permutations for a given length

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
    class Program
    {
        public static int flag = 0;
        static void Main(string[] args)
        {
            int numberOfCircles = 4;
            int stringLength = 2 * numberOfCircles;
            int counter = 0;
            string num = "";
            for (int i = 0; i < stringLength; i++)             
            {                 
                num = num + "1";             
            }             
            if (stringLength > 0)
            {
                for (int i = Convert.ToInt32(num, 2);  ; i++)
                {
                    if (i < 0)                     
                    {                         
                       Console.WriteLine("Too big number!!!");                         
                       break;                     
                    }                     
                    int columnNumber = i;                     
                    char[] alphabets = { ')', '(' };                     
                    string columnHeader = "";                     
                    if (columnNumber > 0)
                    {
                        while (columnNumber > 0)
                        {
                            columnHeader = columnHeader + alphabets[columnNumber % alphabets.Length].ToString();
                            if (columnNumber % alphabets.Length == 0)
                            {
                                columnNumber--;
                            }
                            columnNumber = columnNumber / alphabets.Length;
                        }
                    }
                    if (columnHeader.Length > stringLength)
                    {
                        break;
                    }
                    else
                    {
                        if (CheckValidOccurrence(Reverse(columnHeader)))
                        {
                            Console.WriteLine(i + " - " + Reverse(columnHeader));
                            counter++;
                            if (flag == 1)
                                break;
                            //Console.ReadLine();
                        }
                    }
                }
            }
            Console.WriteLine("Total number of combinations = " + counter);
        }
        public static string Reverse(string text)
        {
            if (text == null) return null;
            char[] array = text.ToCharArray();
            Array.Reverse(array);
            return new string(array);
        }
        public static bool CheckValidOccurrence(string text)
        {
            int sum = 0; int final = 0;
            for (int i = 0; i < text.Length; i++)             
            {                 
                  if (text[i] == '(')                 
                  {                     
                    sum++;                     
                    if (sum > 1)
                    {
                      final = 1;
                    }
                  }
                  else
                  {
                    sum--;
                  }
                  if (sum < 0)                     
                     return false;             
            }             
            if (sum == 0 && text.Length > 0)
            {
                if (final == 0)
                    flag = 1;
                return true;
            }
            else
                return false;
        }
    }
}
Output
=======
270 - (((())))
278 - ((()()))
282 - ((())())
284 - ((()))()
294 - (()(()))
298 - (()()())
300 - (()())()
306 - (())(())
308 - (())()()
326 - ()((()))
330 - ()(()())
332 - ()(())()
338 - ()()(())
340 - ()()()()
Total number of combinations = 14
Press any key to continue . . ..
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

One Response to Counting the number of valid bracket permutations for a given length

  1. Saikat says:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace ConsoleApplication1
    {
    class Program
    {
    public static int count = 0;
    static void Main(string[] args)
    {
    int numberOfOnes = 4;
    int numberOfZeroes = 4;
    int length = 8;
    GeneratePermutation(numberOfOnes, numberOfZeroes, 0, 0, length, "");
    Console.WriteLine("Total number of valid permutations = " + count);
    }

    public static void GeneratePermutation(int numberOfOnesRemaining, int numberOfZeroesRemaining, int numberOfOnesUsed, int numberOfZeroesUsed, int length, string str)
    {
    if (str.Length == length)
    {
    Console.WriteLine(str);
    count++;
    return;
    }

    if (numberOfOnesRemaining > 0)
    {
    GeneratePermutation(numberOfOnesRemaining - 1, numberOfZeroesRemaining, numberOfOnesUsed + 1, numberOfZeroesUsed, length, str + "(");
    }

    if (numberOfZeroesRemaining > 0 && numberOfOnesUsed > numberOfZeroesUsed)
    {
    GeneratePermutation(numberOfOnesRemaining, numberOfZeroesRemaining - 1, numberOfOnesUsed, numberOfZeroesUsed + 1, length, str + ")");
    }
    }
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s