Algorithms- all valid Parentheses subsequences

Question

I recently came across a problem of finding all possible subsequences of valid parantheses where a parentheses is described by a number like -x x,where '-x' indicates opening and 'x' represents closing and -x s x also represents a valid parentheses where 's' is a valid parentheses.

ex-For example, "-1 -2 2 -3 -4 4 3 1" is a balanced bracket-pair sequence, but "-1 -2 1 2" is not and -1 -2 9 2 -3 -4 3 4 8 8 1 gives 12

i am trying but i am not been able to come up with a recursive relation for this problem.Any help would be appreciated.Thanks.

score 0 · Answer 1 · edited Aug 28 '21 at 14:27

def findPairsOfParentheis(collection):

    count = 0
    flag = False
    othercount = 0
    for i in collection:

        if i.startswith('-'):
            if flag:
                othercount += 1 
                continue
            else:
                othercount += 1
                flag = True
        else:
            if flag:
                if othercount > 1:
                    othercount -= 1
                    count += 1
                else:
                    othercount = 0
                    flag = False
                    count += 1
            else:
                continue
                

    return count

The code is Python and it prints the number of pairs of parentheses.

score 0 · Accepted Answer · answered Dec 10 '14 at 06:14

Any valid balanced parenthetic sequence has a unique shortest balanced prefix (which might be the entire sequence). That prefix must be of the form ( S ) where S is a balanced sequence. Moreover, the rest of the original sequence must either be empty or a balanced sequence. Consequently, any balanced sequence can be written as:

S = ( S₁ ) S₂

where S₁ and S₂ are both shorter balanced sequences.

This leads to a simple recursive generator. It also demonstrates that the number of valid parenthetic sequences of length 2k is the Catalan number of index k (using the standard recurrence relation for Catalan numbers which is too hard to type here without latex).

In the numeric form, you'd need to use:

S = -1 S₁' 1 S₂'

where the indices in S₁' are obtained from S₁ by incrementing by one, and S₂' is obtained from S₂ by incrementing by the largest index in S₁' (which is one more than half the length of S₁).

What do you mean by " the indices in S1' are obtained from S1 by incrementing by one, and S2' is obtained from S2 by incrementing by the largest index in S1' " Can you plz elaborate ? — CPPCoder, Dec 13 '14 at 17:48
@CPPCoder: I think I answered the question posted, which is not the same as the CodeChef challenge which might be what OP and you are interested in. Or at least I answered one possible interpretation of the question; in particular, I was assuming a canonical numbering of parentheses and my note about how to derive the numbers is related to generating canonical numberings. I believe the CodeChef challenge is happy to allow any pair of parentheses to have any number at all. But it is about finding subsequences, not about generating all possibilities. — rici, Dec 13 '14 at 20:48

score 0 · Answer 3 · answered Dec 10 '14 at 06:22

You can use two stacks, negStack and posStack; negStack is initialized with all of the negative parentheses in order with -1 at the top, posStack is empty to start. Whenever you pop a negative parenthesis from negStack you push its positive counterpart to posStack.

On each recursive call you can either pop from negStack (assuming it's non-empty) and push to postStack, or you can pop from posStack (assuming it's non-empty). This means that your recursive method would look like

void recurrence(Stack negStack, Stack posStack) {
  // first recursive call: pop from negStack
  int neg = negStack.pop();
  posStack.push(-1 * neg);
  recurrence(negStack, posStack);

  // restore stacks
  posStack.pop();
  negStack.push(neg);

  // second recursive call: pop from posStack
  int pos = posStack.pop();
  recurrence(negStack, posStack);

  // restore stacks
  posStack.push(pos);
}

I've omitted the checks to see if negStack or posStack is empty, as well as the code to store and print the results etc (e.g. you could use another stack to store the parentheses' running total, then print the stack contents when negStack and posStack are empty).

score 0 · Answer 4 · edited Aug 28 '21 at 14:29

Using knowledge of the Catalan number and a simple factorial function you can get this in JavaScript.

function BracketCombinations(num) {  
  let number = 0;
  number = num; 

  return (((FirstFactorial(2*number))/((FirstFactorial(number+1))*FirstFactorial(number)))); 
}
function FirstFactorial(number) {
  var factorial = 1;
  for (var i = 1; i <= number; i++) {
    factorial *= i;
  }

  return factorial;
}

Algorithms- all valid Parentheses subsequences

4 Answers4