CODEWITHSUNDEEP
algorithmpuzzlecatalan
Jexcy
Jexcy

Reputation: 594

How to print all possible balanced parentheses for an expression?

For example, with elements a,b,c,d, there are 5 possible ways to take neighboring elements and reduce them into a single element, where exactly two elements must be combined at a time (below represented by parentheses):

(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))

The first example multiplies a*b, then multiplies that product by c, then multiplies that product by d. The second example first multiplies b*c, then multiplies that product by a, then multiplies that product by d.

Any valid parenthesized expression of 2n elements will necessarily have n ( and n ) with the property that, reading from left to right, there are always at least as many ( as ).

I know that for n numbers, the number of ways is the (n-1)th Catalan number. But how does one accurately generate all the resulting groupings?

Thanks

(As an aside: There are over 160 equivalent formulations of this problem, all based on different combinatorial objects enumerated by the Catalan Numbers. For the most up to date list of these, see Richard Stanley's Catalan Addendum.)

Upvotes: 9

Views: 10428

Answers (9)

user515430
user515430

Reputation: 316

The initial left parenthesis has a unique matching right parenthesis such that what is between the two parentheses and what comes after are both valid expressions. This leads to a simple recursive solution here expressed in Scala.

def catalan(n: Int): List[String] =
    if (n == 0) List("")
    else
        for {
            k <- (0 to n - 1).toList
            first <- catalan(k)
            rest <- catalan(n - 1 - k)
        } yield "a" + first + "b" + rest

Here I'm using "a" for left parenthesis and "b" for right parenthesis.

catalan(0)               List()
catalan(1)               List(ab)
catalan(2)               List(abab, aabb)
catalan(3)               List(ababab, abaabb, aabbab, aababb, aaabbb) 
catalan(5).size          42

Upvotes: 0

NNP
NNP

Reputation: 3451

Here is C# version of generating all possible balanced parenthesized strings from the given n+1 factors.

Note solution for the problem basically satisfies the Catalan recursive relationship (for more details, you may refer to http://codingworkout.blogspot.com/2014/08/all-possible-paranthesis.html, http://en.wikipedia.org/wiki/Catalan_number)

string[] CatalanNumber_GeneratingParanthesizedFactorsRecursive(string s)
        {
            if(s.Length == 1)
            {
                return new string[] {s};
            }
            if(s.Length == 2)
            {
                string r = "(" + s + ")";
                return new string[] { r };
            }
            List<string> results = new List<string>();
            for (int i = 1; i < s.Length; i++)
            {
                var r1 = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                    s.Substring(0, i));
                var r2 = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                    s.Substring(i));
                foreach(var s1 in r1)
                {
                    foreach(var s2 in r2)
                    {
                        string r = "(" + s1 + s2 + ")";
                        results.Add(r);
                    }
                }
            }
            return results.ToArray();
        }

where 

string[] CatalanNumber_GeneratingParanthesizedFactors(string s)
        {
            s.ThrowIfNullOrWhiteSpace("s");
            if(s.Length == 1)
            {
                return new string[] {s};
            }
            var r = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                s);
            return r;
        }

And Unit tests are

[TestMethod]
        public void CatalanNumber_GeneratingParanthesizedFactorsTests()
        {
            var CatalanNumbers = new int[] { 1, 1, 2, 5, 14, 42, 132, 429, 
                1430, 4862, 16796 };
            string input = "";
            for (int i = 1; i <= 10; i++)
            {
                input += i;
                var results2 = this.CatalanNumber_GeneratingParanthesizedFactors(input);
                Assert.AreEqual(results2.Length, CatalanNumbers[input.Length-1]);
                Debug.WriteLine("-----------------------------------------------");
                foreach (string ss in results2)
                {
                    Debug.WriteLine(ss);
                }
            }
            string s = "a";
            var r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            Assert.AreEqual(r.Length, 1);
            Assert.AreEqual(s, r[0]);
            s = "ab";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            Assert.AreEqual("(ab)", r[0]);
            s = "abc";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            string[] output = new string[] { "(a(bc))", "((ab)c)" };
            Assert.AreEqual(2, r.Length);
            foreach(var o in output)
            {
                Assert.AreEqual(1, r.Where(rs => (rs == o)).Count());
            }
            s = "abcd";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);

            output = new string[] { "(a(b(cd)))", "(a((bc)d))", "((ab)(cd))", "(((ab)c)d)", "((a(bc))d)"};
            Assert.AreEqual(5, r.Length);
            foreach (var o in output)
            {
                Assert.AreEqual(1, r.Where(rs => (rs == o)).Count());
            }
        }

Upvotes: 0

learner
learner

Reputation: 308

*

**Run this to generate all balanced parantheses:
//sudosuhan
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAX_SIZE 200
void _printParenthesis(int pos, int n1, int open1, int close1, int n2, int open2, int close2, int n3, int open3, int close3);
void printParenthesis(int n1 , int n2 , int n3 )
{
  if(n1 > 0 || n2 > 0 || n3 > 0)
     _printParenthesis(0, n1, 0, 0, n2, 0, 0, n3, 0, 0);
  return;
}
void _printParenthesis(int pos, int n1, int open1, int close1, int n2, int open2, int close2, int n3, int open3, int close3)
{
  static char str[MAX_SIZE];     

  if(close1 == n1 && close2 == n2 && close3 == n3 ) 
  {
    printf("%s \n", str);
    return;
  }
  else
  {
    bool run1 = open1 > close1;
    bool run2 = open2 > close2;
    bool run3 = open3 > close3;
    if(run3)
    {
      str[pos] = ')';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3, close3+1);

      if(open3 < n3)
      {
      str[pos] = '(';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);
      }
    }
    else if(run2 && !run3)
    {
      str[pos] = '}';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2+1, n3, open3, close3);

      if(open3 < n3)
      {
      str[pos] = '(';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);
      }
      if(open2 < n2)
      {
      str[pos] = '{';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);
      }
    }
    else if(run1 && !run2 && !run3)
    {
      str[pos] = ']';
      _printParenthesis(pos+1, n1, open1, close1+1, n2, open2, close2, n3, open3, close3);

      if(open3 < n3)
      {
      str[pos] = '(';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);
      }
      if(open2 < n2)
      {
      str[pos] = '{';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);
      }
      if(open1 < n1)
      {
      str[pos] = '[';
      _printParenthesis(pos+1, n1, open1+1, close1, n2, open2, close2, n3, open3, close3);
      }
    }
    else if(!run1 && !run2 && !run3)
    {
      if(open3 < n3)
      {
       str[pos] = '(';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);
      }
      if(open2 < n2)
      {
      str[pos] = '{';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);
      }
      if(open1 < n1)
      {
      str[pos] = '[';
      _printParenthesis(pos+1, n1, open1+1, close1, n2, open2, close2, n3, open3, close3);
      }
    }

  }
}
/* driver program to test above functions */
int main()
{
  int n1, n2, n3;
  n1 = 6;
  n2 = 1;
  n3 = 1;
  printParenthesis(n1, n2, n3);
  return 0;
}**

*

Upvotes: 1

Adil Saeed
Adil Saeed

Reputation: 11

import java.util.ArrayList;


public class Parantheses {

    private ArrayList<String> parStringList;
    private int total;

    public void exploreParantheses(String parString,int leftCnt,int rightCnt)
    {
        if (leftCnt < total)
        {
            exploreParantheses(parString + "(", leftCnt+1, rightCnt);
        }
        if ((rightCnt < total) &&(rightCnt < leftCnt))
        {
            exploreParantheses(parString + ")", leftCnt, rightCnt+1);
        }
        else if (rightCnt == total)
        {
            parStringList.add(parString);
        }
    }
    public ArrayList<String> generateParanthesis(int numPars)
    {
        this.total = numPars;
        this.parStringList = new ArrayList<String>();
        exploreParantheses("", 0, 0);
        return this.parStringList;
    }
    public static void main(String args[])
    {
        ArrayList<String> par;
        par = (new Parantheses()).generateParanthesis(6);
        for (String str: par)
            System.out.println(str);
    }
}

Upvotes: 1

Arvind
Arvind

Reputation: 478

And, here is some C++ code for the same : 

bool is_a_solution( string partial,int n,int k) { 
if(partial.length() == n*2 )  
 return true;
return false;
  }
string constructCandidate(int n,string input,string partial, int k) { 
int xcount=0,ycount=0;
int count;
int i;
string candi;
if(k == 0)  
    return string("(");
else { 
    for(i=0;i<partial.length();i++)  { 
        if( partial[i] == '(') xcount++;
        if( partial[i] == ')') ycount++;
    }
    if( xcount  <n) candi+="(";  
    if( ycount < xcount) candi+=")"; 
    }
return candi;}                                                                                void backTrack(int n,string input, string partial,int k )  { 
int i, numCanditate;
string mypartial;
    if( is_a_solution(partial,n,k)) { 
    cout <<partial<<"\n"; 
 }else {
     string  candi=constructCandidate(n,input,partial,k); 
     for(i=0;i<candi.length();i++) {
         backTrack(n,input,partial+candi[i],k+1); 
     }
 }
void paranthesisPrint(int n){
   backTrack(n,"()", "",0); 
   }

Upvotes: 0

ninjagecko
ninjagecko

Reputation: 91132

There are actually many more than 5 parenthesizations of 4 elements; you don't actually mean "parenthesizations". What you are really asking is the number of different ways N elements can be reduced, or the number of trees you can make out of N elements while still keeping them in order.

This corresponds to subdividing the expression exactly N-1 times. For example in this graphic from wikipedia's http://en.wikipedia.org/wiki/Catalan_number article, if we have 4 elements, there are exactly 5 ways to apply a binary operator to it (there will need to be exactly 3 applications, hence there are exactly 3 nodes):

enter image description here

For example, ((a*b)*c)*d, (a*(b*c))*d, (a*b)*(c*d), a*((b*c)*d), a*(b*(c*d))

Here's some concise python code to do it:

def associations(seq, **kw):
    """
        >>> associations([1,2,3,4])
        [(1, (2, (3, 4))), (1, ((2, 3), 4)), ((1, 2), (3, 4)), ((1, (2, 3)), 4), (((1, 2), 3), 4)] 
    """
    grouper = kw.get('grouper', lambda a,b:(a,b))
    lifter = kw.get('lifter', lambda x:x)

    if len(seq)==1:
        yield lifter(seq[0])
    else:
        for i in range(len(seq)):
            left,right = seq[:i],seq[i:] # split sequence on index i

            # return cartesian product of left x right
            for l in associations(left,**kw):
                for r in associations(right,**kw):
                    yield grouper(l,r)

Note how you can substitute interesting function for grouper with this code, e.g. grouper=list, or grouper=Tree, or grouper=....

Demo:

for assoc in associations('abcd'):
    print assoc

('a', ('b', ('c', 'd')))
('a', (('b', 'c'), 'd'))
(('a', 'b'), ('c', 'd'))
(('a', ('b', 'c')), 'd')
((('a', 'b'), 'c'), 'd')

Upvotes: 8

btilly
btilly

Reputation: 46455

Here is actual code in Python, using generators to avoid using too much memory.

#! /usr/bin/python

def parenthesized (exprs):
    if len(exprs) == 1:
        yield exprs[0]
    else:
        first_exprs = []
        last_exprs = list(exprs)
        while 1 < len(last_exprs):
            first_exprs.append(last_exprs.pop(0))
            for x in parenthesized(first_exprs):
                if 1 < len(first_exprs):
                    x = '(%s)' % x
                for y in parenthesized(last_exprs):
                    if 1 < len(last_exprs):
                        y = '(%s)' % y
                    yield '%s%s' % (x, y)

for x in parenthesized(['a', 'b', 'c', 'd']):
    print x

Upvotes: 10

PengOne
PengOne

Reputation: 48398

Use recursion

   for each balanced expression of n-1 parentheses 
     for each pos i from 0 to m of an expression
       add '('
       for each pos  j from i + 1 to m
          add ')' if expression is balanced

The order you will get is the following:

n=0: 

n=1: ()

n=2: []() , [()]

n=3: {}[]() , {[]}() , {[]()} , {}[()] , {[()]}

Here I'm changing the parens each time (,[,{ to highlight how the algorithm works.

Upvotes: 4

Adithya Surampudi
Adithya Surampudi

Reputation: 4454

Recursion would be the way to go

split abcd into 

(a) (bcd)
(ab) (cd)
(abc) (d)

These are some of the possibilities

Now recursively you can split each string(ignore the parenthesis while splitting) say for (bcd) one possibility

(b) (cd)

so now another combination is

((a)(b)(cd))

You can stop the recursion tree once you get a string with only one alphabet

Upvotes: 1

Related Questions