C++ Program To Count Distinct Regular Bracket Sequences Which Are Not N Periodic

The objective is to determine the number of unique bracket sequences that can be generated using 2 * N brackets, where N is a given integer, while ensuring that the sequence is not N-periodic. In the context of this problem, a bracket sequence is considered N-periodic if it can be split into two equal substrings, both forming valid bracket sequences.

A standard bracket sequence is defined as follows:

• ✅ An empty string constitutes a valid regular bracket sequence.
• ✅ The concatenation of two regular bracket sequences, denoted as s + t, results in a regular bracket sequence when both s and t individually are regular bracket sequences.

Let's consider an instance where N is equal to 3. This piece of code will generate the subsequent five distinctive, non-three-periodic regular bracket sequences with a length of six: (()), (), (), (), and .

Problem Statement:

Determining the number of distinct regular bracket sequences with a length of 2N that do not exhibit N-periodicity is the objective when provided with an integer N. If a sequence can be represented by a string S that repeats M times, with each repetition having a length of N and M being greater than 1, then it is classified as N-periodic.

A string that can be transformed into a correct mathematical expression by interspersing "1" and "+" between the original characters is identified as a regular bracket sequence. For instance, "()" is a valid regular sequence, while both ")(" and "(" are not considered regular bracket sequences.

Approach:

The idea is to first compute the total number of length 2 * N regular bracket sequences that can exist and then deduct from that total the number of N-periodic bracket sequences. The steps are listed below:

• ✅ Utilizing the Catalan number formula, we can determine the quantity of regular bracket sequences with length 2*N.
• ✅ An even number N is required for a sequence of length 2*N to be N periodic; otherwise, the sequence cannot be both regular and have a period of N simultaneously.
• ✅ Both of the length N subsequences should be regular because a sequence cannot be made regular by concatenating two similar non-regular bracket sequences.
• ✅ To obtain the desired outcome, subtract the number of regular bracket sequences of length 2*N from the number of regular bracket sequences of length N (if N is even).

C++ Implementation:

This C++ solution tackles the problem through a brute-force strategy. In this technique, it generates all possible bracket sequences and calculates their N-periodicity by tallying instances where it is not. However, this method is not efficient for handling larger inputs and is more suitable for smaller inputs because of its exponential time complexity.

C++ Code:

#include <bits/stdc++.h>
using namespace std;

// Function to check if string is N-periodic
bool isNPeriodic(string s, int N) {
   string sub = s.substr(0, N);
   for (int i = N; i < s.size(); i += N) {
      if (sub != s.substr(i, N)) return false;
   }
   return true;
}

// Function to generate all bracket sequences
void generateBracketSequences(string sequence, int openCount, int closeCount, int N, int &totalCount) {
   // If sequence is complete
   if (sequence.size() == 2 * N) {
      if (!isNPeriodic(sequence, N)) totalCount++;
      return;
   }
   
   // Add an open bracket if we have some left
   if (openCount < N) generateBracketSequences(sequence + "(", openCount + 1, closeCount, N, totalCount);
   
   // Add a close bracket if it doesn't make the sequence invalid
   if (closeCount < openCount) generateBracketSequences(sequence + ")", openCount, closeCount + 1, N, totalCount);
}

int main() {
   int N = 4; // Change the value of N as per requirement
   int totalCount = 0;
   generateBracketSequences("", 0, 0, N, totalCount);
   cout << "Count of distinct regular bracket sequences not " << N << "-periodic: " << totalCount;
   return 0;
}

Output:

Count of distinct regular bracket sequences not 4-periodic: 12

Conclusion:

In summary, an intriguing overlap between combinatorics and programming lies in the challenge of enumerating unique regular bracket sequences that do not exhibit N-periodic behavior. We have explored efficient methods for generating and evaluating these sequences through the enhancement of C++ algorithms. We have successfully tackled the task of enumerating such sequences and confirmed their non-N-periodic nature by leveraging techniques such as manipulating strings, recursion, and periodicity validations. Our exploration has shed light on the intricate nature of combinatorial challenges and the efficacy of programming in addressing them. Additionally, our research underscores the importance of algorithmic optimization in managing complex computational problems and the significance of clear code structuring.