Regular Bracket sequence

The correct sequence of the bracket is a string consisting entirely of characters with "brackets" (often considered only parentheses, but this will be considered and the general case of several types of brackets), where each closing brace exists a corresponding opening (and of the same type).

Here we consider the classic problem parenthesis on the right sequence (for brevity hereinafter simply "order") to check the correctness of the number of sequences, all sequences generated by finding the lexicographically next sequence determination $k$ -th sequence in the sorted list of all sequences, and, conversely, determination sequence number. Each of the problems addressed in two ways - when the brackets are allowed only one type, and when several types.

Check for correct

Suppose first allowed only one type of bracket, then check for correct sequence can be a very simple algorithm. May $\rm depth$ - is the current number of open parentheses.Initially $\rm depth = 0$ . We will move from left to right on the line, if the current opening bracket, the increase $\rm depth$ in the unit, otherwise reduce. If in this case when it turns negative, or at the end of the algorithm $\rm depth$ is different from zero, this string is not correct bracketing sequence is different.

If allowed several types of brackets, then the algorithm you want to change. Instead, the meter $\rm depth$ should create a stack, in which we put the parentheses as they become available. If the current character in the string - opening bracket, then we place it on the stack, and if the closing - then check that the stack is not empty, and that on the top bracket is the same type as the current one, and then We reach this bracket from the stack. If any of the conditions are not fulfilled, or at the end of the algorithm the stack was not empty, then the sequence is not the correct bracketing, or is.

Thus, both of these problems, we learned to solve in time $(N)$ .

Number of sequences

formula

The number of correct bracket sequence with one type of brackets can be calculated as the number of Catalan . Those. if there is a $n$ pair of brackets (line length $2n$ ), the number will be:

$\frac{1}{n+1} \cdot C^n_{2n}.$

Suppose now that there is not one, and $k$ types of brackets. Then, each pair of brackets independently of the others may take one of the $k$ types, so we get the following formula:

$\frac{1}{n+1} \cdot C^n_{2n} \cdot k^n.$

dynamic programming

On the other hand, this problem can be approached from the point of view of dynamic programming . Let $d [n]$ - the number of correct bracket sequence of $n$ pairs of brackets. Note that in the first position will always stand open parenthesis. It is clear that in this pair of brackets is some correct bracket sequence; similarly, after this pair of brackets is also correct bracket sequence. Now, to calculate $d [n]$ , Let's brute over how many pairs of brackets $i$ will be inside the first pair, then, respectively, $n-1-i$ a pair of brackets will stand after the first pair. Therefore, the formula for $d [n]$ is:

$d[n] = \sum_{i=0}^{n-1} d[i] \cdot d[n-1-i].$

The initial value of the recursion formula - it $d[0] = 1$ .

Finding all sequences

Sometimes you need to find and display all the correct bracket sequence specified length $n$ (in this case $n$ - it is the length of string).

To do this, you can start with the lexicographically first sequence $((\ldots(())\ldots))$ , and then find the lexicographically each time the following sequence using the algorithm described in the next section.

But if the restrictions are not very large ( $n$ up to $10-12$ ), you can do much easier. We find all kinds of permutations of these brackets (this is useful next_permutation () function), they will be $C {2n} ^ n$ , and each check on the correctness of the algorithm described above, in the case of correctness derive the current sequence.

Also, the process of finding all sequences can be issued in the form of a recursive enumeration with clipping (that ideally can be adjusted according to the speed of the first algorithm).

Finding the next sequence

Here we consider only the case of one type of brackets.

For a given proper bracketing sequence is required to find the correct sequence of the bracket, which is next in the lexicographical order after the current (or to give "No solution", if such exists).

It is clear that the whole algorithm is as follows: find a rightmost opening parenthesis, that we have the right to change at closing (as to the correctness of this place is not broken), and the whole line is replaced by the lexicographically minimum rest right: that is, as a opening parenthesis, then all of the remaining closing brackets. In other words, we try to remain unchanged as the longest prefix of the original sequence, and this sequence the suffix is replaced by the lexicographically minimum.

It remains to learn to look for that same position of the first changes. To do this, we will go on the line from right to left, and maintain a balance $\rm depth$ of open and closed brackets (at the meeting opening bracket will decrease $\rm depth$ , and at the closing - increase). If at any point we are on the opening parenthesis, and the balance after the processing of the character is greater than zero, then we have found the right-most position from which we can begin to change the sequence (in fact, $\rm depth > 0$ means that the left has not closed yet parenthesis) . We put the current position closing parenthesis, then the maximum possible number of opening brackets, and then all of the remaining closing brackets - the answer is found.

If we watched the whole line and have not found a suitable position, the current sequence - the maximum, and there is no answer.

The implementation of the algorithm:

string s;
cin >> s;
int n = (int) s.length();
string ans = "No solution";
for (int i=n-1, depth=0; i>=0; --i) {
 if (s[i] == '(')
  --depth;
 else
  ++depth;
 if (s[i] == '(' && depth > 0) {
  --depth;
  int open = (n-i-1 - depth) / 2;
  int close = n-i-1 - open;
  ans = s.substr(0,i) + ')' + string (open, '(') + string (close, ')');
  break;
 }
}
cout << ans;

Thus, we have solved this problem for $(N)$ .

sequence Number

Here, let $n$ - the number of pairs of brackets in the sequence. Required for a given proper bracketing sequence to find its number in the list lexicographically ordered the correct bracket sequence.

Let us learn to consider supporting the dynamics of $d[i][j]$ which $i$ - the length of the bracket sequence (it "semiregular": all the closing bracket has an opening pair, but not all open parentheses are closed), $j$ - the balance (ie the difference between the number of opening and closing brackets), $d[i][j]$ - the number of such sequences.When calculating these dynamics, we believe that the brackets are only one type.

Read this dynamic as follows. Let $d[i][j]$ - the value that we want to calculate. If $i=0$ the answer is clear right away: $d[0][0] = 1$ all the rest $d [0] [j] = 0$ . Now suppose that $i > 0$ , then mentally Let's brute over, which was equal to the last character of this sequence. If he is '(' something to that character, we were able to $(i-1,j-1)$ . If it is equal to ')', then it was the previous state $(i-1,j+1)$ . Thus we get the formula:

$d[i][j] = d[i-1][j-1] + d[i-1][j+1]$

(assuming that all values $d[i][j]$ at negative $j$ zero). Thus, this dynamic can we count for $O (n ^ 2)$ .

Let us now turn to the solution of the problem.

First, let only allowed braces one type. Zavedёm counter $\rm depth$ nesting in parentheses, and will move in sequence from left to right. If the current symbol $s[i]$ ( $i=0 \ldots 2n-1$ ) is' ( 'we increase $\rm depth$ at 1 and go to the next character. If the current character is')', then we must add to the response $d[2n-i-1][\rm depth+1]$ , thereby taking into account that the symbol would be in this position ' ( '(which would lead to lower lexicographical sequence than the current), then we reduce $\rm depth$ by one.

Suppose now that the brackets are allowed multiple $k$ types. Then, when considering the current character $s[i]$ to the conversion $\rm depth$ we need to go through all brackets that are less than the current character, to try to put the bracket at the current position (thereby obtaining a new balance $\rm ndepth = \rm depth \pm 1$ ), and and add to account number corresponding to the "tails" - completions (which have a length $2n-i-1$ , balance $\rm ndepth$ and $k$ types of brackets). It is alleged that the formula for this quantity has the form:

$d[2n-i-1][{\rm ndepth}] \cdot k^{ (2n-i-1 - {\rm [...]$

This formula is derived from the following considerations. First, we "forget" about the fact that there are several types of braces, and just take the answer from $d[2n-i-1][{\rm ndepth}]$ . Now calculate how to change an answer because of the $k$ types of brackets. We have an $2n-i-1$ undefined position of which $\rm ndepth$ are staples, closing some of the public before - hence, the type of bracket, we can not be varied. But all the other brackets (and they will $(2n-i-1 - {\rm ndepth})/2$ steam) can be of any $k$ type, so the answer is multiplied by the power of the number $k$ .

Finding $k$ th sequence

Here, let $n$ - the number of pairs of brackets in the sequence. In this problem on the set $k$ you want to search $k$ -s correct bracket sequence in the list lexicographically ordered sequence.

As in the previous section, we calculate the dynamics $d[i][j]$ - the number of correct bracket sequence length $i$ with the balance $j$ .

Suppose first allowed only brackets of type.

We move on the characters of the string, with $0$ th at $2n-1$ th. As in the previous problem, let us have a counter $\rm depth$ - current depth of nesting in parentheses. In each of the current position will be possible to touch a symbol - an opening parenthesis or closing. Suppose we want to put an opening parenthesis here, then we have to look at the value $d[i+1][\rm depth+1]$ . If it is $\ Ge k$ , then we put in the current position of the opening bracket, increasing $\rm depth$ by one and move on to the next character.Otherwise, we will take away from the $k$ value $d[i+1][\rm depth+1]$ , put the closing bracket and reduce the value $\rm depth$ . In the end, we obtain the required sequence of the bracket.

The implementation of the Java language using long arithmetic:

int n;  BigInteger k;  // входные данные
 
BigInteger d[][] = new BigInteger [n*2+1][n+1];
for (int i=0; i<=n*2; ++i)
 for (int j=0; j<=n; ++j)
  d[i][j] = BigInteger.ZERO;
d[0][0] = BigInteger.ONE;
for (int i=0; i<n*2; ++i)
 for (int j=0; j<=n; ++j) {
  if (j+1 <= n)
   d[i+1][j+1] = d[i+1][j+1].add( d[i][j] );
  if (j > 0)
   d[i+1][j-1] = d[i+1][j-1].add( d[i][j] );
 }
 
String ans = new String();
if (k.compareTo( d[n*2][0] ) > 0)
 ans = "No solution";
else {
 int depth = 0;
 for (int i=n*2-1; i>=0; --i)
  if (depth+1 <= n && d[i][depth+1].compareTo( k ) >= 0) {
   ans += '(';
   ++depth;
  }
  else {
   ans += ')';
   if (depth+1 <= n)
    k = k.subtract( d[i][depth+1] );
   --depth;
  }
}

Suppose now allowed more than one, and $k$ types of brackets. Then the algorithm solutions will be different from the previous case only in that we have to multiply the value $D[i+1][\rm ndepth]$ by an amount $k^{(2n-i-1- \rm ndepth)/2}$ to take into account that this balance can be brackets of various types, and the pair of parentheses in this balance will only be $2n-i-1- \rm ndepth$ because $\rm ndepth$ the brackets are closing for opening brackets that are that is the residue (and their types because we can not be varied).

The implementation of the Java language in the case of two types of brackets - round and square:

int n;  BigInteger k;  // входные данные
 
BigInteger d[][] = new BigInteger [n*2+1][n+1];
for (int i=0; i<=n*2; ++i)
 for (int j=0; j<=n; ++j)
  d[i][j] = BigInteger.ZERO;
d[0][0] = BigInteger.ONE;
for (int i=0; i<n*2; ++i)
 for (int j=0; j<=n; ++j) {
  if (j+1 <= n)
   d[i+1][j+1] = d[i+1][j+1].add( d[i][j] );
  if (j > 0)
   d[i+1][j-1] = d[i+1][j-1].add( d[i][j] );
 }
 
String ans = new String();
int depth = 0;
char [] stack = new char[n*2];
int stacksz = 0;
for (int i=n*2-1; i>=0; --i) {
 BigInteger cur;
 // '('
 if (depth+1 <= n)
  cur = d[i][depth+1].shiftLeft( (i-depth-1)/2 );
 else
  cur = BigInteger.ZERO;
 if (cur.compareTo( k ) >= 0) {
  ans += '(';
  stack[stacksz++] = '(';
  ++depth;
  continue;
 }
 k = k.subtract( cur );
 // ')'
 if (stacksz > 0 && stack[stacksz-1] == '(' && depth-1 >= 0)
  cur = d[i][depth-1].shiftLeft( (i-depth+1)/2 );
 else
  cur = BigInteger.ZERO;
 if (cur.compareTo( k ) >= 0) {
  ans += ')';
  --stacksz;
  --depth;
  continue;
 }
 k = k.subtract( cur );
 // '['
 if (depth+1 <= n)
  cur = d[i][depth+1].shiftLeft( (i-depth-1)/2 );
 else
  cur = BigInteger.ZERO;
 if (cur.compareTo( k ) >= 0) {
  ans += '[';
  stack[stacksz++] = '[';
  ++depth;
  continue;
 }
 k = k.subtract( cur );
 // ']'
 ans += ']';
 --stacksz;
 --depth;
}

BRACES

Wednesday, 18 May 2016

some theory

Regular Bracket sequence

Check for correct

Number of sequences

formula

dynamic programming

Finding all sequences

Finding the next sequence

sequence Number

Finding $k$ th sequence

Wednesday, 18 May 2016

some theory

Regular Bracket sequence

Check for correct

Number of sequences

formula

dynamic programming

Finding all sequences

Finding the next sequence

sequence Number

Finding th sequence

Finding $k$ th sequence