// to follow SensiBol Audio Technologies
//https://www.cdeep.iitb.ac.in/slides/S18/ENT602/ENT602-L22.pdf
////////////Catalan numbers form a sequence of integers that appear in various counting problems, particularly those involving recursion and binary trees.The nth Catalan number, denoted as Cn, is the solution to many combinatorial problems.The sequence starts with 1, 1, 2, 5, 14, 42, 132, 429...
////////////Definition and Formula:
////////////The nth Catalan number, Cn, can be calculated using the following formula:
////////////Cn = (2n)! / ((n + 1)! * n!)
////////////Alternatively, it can be defined recursively:
////////////C0 = 1
////////////Cn+1 = Σ(Ci* Cn-i) for i from 0 to n
////////////Applications:
////////////Balanced Parentheses:
////////////Cn represents the number of ways to arrange n pairs of parentheses such that they are correctly matched.
////////////Binary Trees:
////////////Cn counts the number of full binary trees with n+1 leaves.
////////////Triangulations:
////////////Cn-2 represents the number of ways to triangulate a convex polygon with n sides.
////////////Dyck Paths:
////////////Cn counts the number of paths on an n x n grid that stay above the main diagonal.
////////////Other Applications:
////////////Catalan numbers also appear in problems related to matrix chain multiplication, Young tableaux, and more.
///https://en.wikipedia.org/wiki/Catalan_number
///https://en.wikipedia.org/wiki/Matrix_chain_multiplication
// // // // // // Matrix chain multiplication (or the matrix chain ordering problem[1]) is an optimization problem concerning the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved. The problem may be solved using dynamic programming.
// // // // // // There are many options because matrix multiplication is associative. In other words, no matter how the product is parenthesized, the result obtained will remain the same. For example, for four matrices A, B, C, and D, there are five possible options:
// // // // // // ((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD)).
// // // // // // Although it does not affect the product, the order in which the terms are parenthesized affects the number of simple arithmetic operations needed to compute the product, that is, the computational complexity. The straightforward multiplication of a matrix that is X × Y by a matrix that is Y × Z requires XYZ ordinary multiplications and X(Y − 1)Z ordinary additions. In this context, it is typical to use the number of ordinary multiplications as a measure of the runtime complexity.
// // // // // // If A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix, then
// // // // // // computing (AB)C needs (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations, while
// // // // // // computing A(BC) needs (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
// // // // // // Clearly the first method is more efficient. With this information, the problem statement can be refined as "how to determine the optimal parenthesization of a product of n matrices?" The number of possible parenthesizations is given by the (n–1)th Catalan number, which is O(4n / n3/2), so checking each possible parenthesization (brute force) would require a run-time that is exponential in the number of matrices, which is very slow and impractical for large n. A quicker solution to this problem can be achieved by breaking up the problem into a set of related subproblems.
// // // // // // A dynamic programming algorithm
// // // // // // To begin, let us assume that all we really want to know is the minimum cost, or minimum number of arithmetic operations needed to multiply out the matrices. If we are only multiplying two matrices, there is only one way to multiply them, so the minimum cost is the cost of doing this. In general, we can find the minimum cost using the following recursive algorithm:
// // // // // // Take the sequence of matrices and separate it into two subsequences.
// // // // // // Find the minimum cost of multiplying out each subsequence.
// // // // // // Add these costs together, and add in the cost of multiplying the two result matrices.
// // // // // // Do this for each possible position at which the sequence of matrices can be split, and take the minimum over all of them.
// // // // // // For example, if we have four matrices ABCD, we compute the cost required to find each of (A)(BCD), (AB)(CD), and (ABC)(D), making recursive calls to find the minimum cost to compute ABC, AB, CD, and BCD. We then choose the best one. Better still, this yields not only the minimum cost, but also demonstrates the best way of doing the multiplication: group it the way that yields the lowest total cost, and do the same for each factor.
// // // // // // However, this algorithm has exponential runtime complexity making it as inefficient as the naive approach of trying all permutations. The reason is that the algorithm does a lot of redundant work. For example, above we made a recursive call to find the best cost for computing both ABC and AB. But finding the best cost for computing ABC also requires finding the best cost for AB. As the recursion grows deeper, more and more of this type of unnecessary repetition occurs.
// // // // // // One simple solution is called memoization: each time we compute the minimum cost needed to multiply out a specific subsequence, we save it. If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it. Since there are about n2/2 different subsequences, where n is the number of matrices, the space required to do this is reasonable. It can be shown that this simple trick brings the runtime down to O(n3) from O(2n), which is more than efficient enough for real applications. This is top-down dynamic programming.
// // // // // // The following bottom-up approach[2] computes, for each 2 ≤ k ≤ n, the minimum costs of all subsequences of length k using the costs of smaller subsequences already computed. It has the same asymptotic runtime and requires no recursion.
// // // // // // Pseudocode:
// // // // // // // Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
// // // // // // MatrixChainOrder(int dims[])
// // // // // // {
// // // // // // // length[dims] = n + 1
// // // // // // n = dims.length - 1;
// // // // // // // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
// // // // // // // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
// // // // // // // The cost is zero when multiplying one matrix
// // // // // // for (i = 1; i <= n; i++)
// // // // // // m[i, i] = 0;
// // // // // // for (len = 2; len <= n; len++) { // Subsequence lengths
// // // // // // for (i = 1; i <= n - len + 1; i++) {
// // // // // // j = i + len - 1;
// // // // // // m[i, j] = MAXINT;
// // // // // // for (k = i; k <= j - 1; k++) {
// // // // // // cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
// // // // // // if (cost < m[i, j]) {
// // // // // // m[i, j] = cost;
// // // // // // s[i, j] = k; // Index of the subsequence split that achieved minimal cost
// // // // // // }
// // // // // // }
// // // // // // }
// // // // // // }
// // // // // // }
// // // // // // Note: The first index for dims is 0 and the first index for m and s is 1.
// // // // // // A Python implementation using the memoization decorator from the standard library:
// // // // // // from functools import cache
// // // // // // def matrix_chain_order(dims: list[int]) -> int:
// // // // // // @cache
// // // // // // def a(i, j):
// // // // // // return min((a(i, k) + dims[i] * dims[k] * dims[j] + a(k, j)
// // // // // // for k in range(i + 1, j)), default=0)
// // // // // // return a(0, len(dims) - 1)
//////////////////using System;
//////////////////using System.Collections.Generic;
//////using System.Text;
//TRYING TO RETAIN FORESTS ORDERING OF SYMBOLS
public class TreeGroupingGenerator___CATALANING______BRACKETING_REGROUPING_COPILOTS___CARTESIAN_FOREST_CORRECTED
{
public static StringBuilder PUBLIC_STATIC_STRINGBUILDER____RAW_CATALANING___CATALANING______BRACKETING_REGROUPING_COPILOTS = new StringBuilder();
public static StringBuilder PUBLIC_STATIC_STRINGBUILDER___ONLY_INDIANNOTES_GROUPINGS___CATALANED_TREES______BRACKETING_REGROUPING_COPILOTS = new StringBuilder();
public static string TreeGroupingGenerator___CATALANING______BRACKETING_REGROUPING_COPILOTS_Main(string input_forest_string)
{
PUBLIC_STATIC_STRINGBUILDER____RAW_CATALANING___CATALANING______BRACKETING_REGROUPING_COPILOTS.Clear();
PUBLIC_STATIC_STRINGBUILDER___ONLY_INDIANNOTES_GROUPINGS___CATALANED_TREES______BRACKETING_REGROUPING_COPILOTS.Clear();
string input = input_forest_string.Replace("(", " ").Replace(")", " ").Replace("&", " ");
input = "|" + input.Replace("\r\n", "|").Replace("\n", "|").Replace("\r", "|") + "|";
input = input.Replace("||||", "|").Replace("|||", "|").Replace("||", "|");
var trees = ParseTrees(input);
var allOptionsPerTree = new List<List<string>>();
foreach (var tree in trees)
{
List<string> groupings = new List<string>();
string header = "|" + string.Join(" ", tree);
if (!groupings.Contains(header))
groupings.Add(header);
var bracketedOptions = GenerateGroupings(tree);
foreach (var opt in bracketedOptions)
{
string line = "|" + opt;
if (!groupings.Contains(line))
groupings.Add(line);
}
allOptionsPerTree.Add(groupings);
}
var finalVistaars = CartesianProduct(allOptionsPerTree);
foreach (var v in finalVistaars)
{
PUBLIC_STATIC_STRINGBUILDER____RAW_CATALANING___CATALANING______BRACKETING_REGROUPING_COPILOTS.AppendLine(v);
PUBLIC_STATIC_STRINGBUILDER___ONLY_INDIANNOTES_GROUPINGS___CATALANED_TREES______BRACKETING_REGROUPING_COPILOTS.AppendLine(v);
}
return PUBLIC_STATIC_STRINGBUILDER____RAW_CATALANING___CATALANING______BRACKETING_REGROUPING_COPILOTS.ToString();
}
public static List<string> CartesianProduct(List<List<string>> lists)
{
List<string> results = new List<string> { "" };
foreach (var treeOptions in lists)
{
List<string> newResults = new List<string>();
foreach (var existing in results)
{
foreach (var option in treeOptions)
{
string combined = (existing + " " + option).Trim();
if (!newResults.Contains(combined))
newResults.Add(combined);
}
}
results = newResults;
}
return results;
}
public static string ReformatAndExpandForestSyntax_Stagewise(string input)
{
var output = new StringBuilder();
string cleanedInput = "|" + input.Replace("\r\n", "|").Replace("\n", "|").Replace("\r", "|") + "|";
cleanedInput = cleanedInput.Replace("||||", "|").Replace("|||", "|").Replace("||", "|");
var trees = cleanedInput.Split(new string[] { "|" }, StringSplitOptions.RemoveEmptyEntries);
var seen = new List<string>();
foreach (var tree in trees)
{
var tokens = tree.Split(new[] { ' ', ',', ';' }, StringSplitOptions.RemoveEmptyEntries);
if (tokens.Length == 0) continue;
string treeOriginal = "|" + string.Join(" ", tokens) + "|";
if (!seen.Contains(treeOriginal)) output.AppendLine(treeOriginal);
string treeStartDash = "|-" + string.Join(" ", tokens) + "|";
if (!seen.Contains(treeStartDash)) output.AppendLine(treeStartDash);
for (int j = 0; j < tokens.Length - 1; j++)
{
var stagedTokens = new List<string>();
for (int k = 0; k < tokens.Length; k++)
{
stagedTokens.Add(tokens[k]);
if (k == j) stagedTokens.Add("-");
}
string stagedTree = "|" + string.Join(" ", stagedTokens) + "|";
if (!seen.Contains(stagedTree)) output.AppendLine(stagedTree);
}
string treeEndDash = "|" + string.Join(" ", tokens) + "-|";
if (!seen.Contains(treeEndDash)) output.AppendLine(treeEndDash);
}
return output.ToString();
}
public static List<List<string>> ParseTrees(string input)
{
List<List<string>> trees = new List<List<string>>();
input = "|" + input.Replace("\r\n", "|").Replace("\n", "|").Replace("\r", "|") + "|";
input = input.Replace("||||", "|").Replace("|||", "|").Replace("||", "|");
var splitTrees = input.Split(new string[] { "|" }, StringSplitOptions.RemoveEmptyEntries);
foreach (var treeContent in splitTrees)
{
var symbols = treeContent.Split(new[] { ' ', ',', ';' }, StringSplitOptions.RemoveEmptyEntries).ToList();
if (symbols.Count > 0 && !trees.Any(x => x.SequenceEqual(symbols)))
{
trees.Add(symbols);
}
}
return trees;
}
public static List<string> GenerateGroupings(List<string> symbols)
{
var results = new List<string>();
Generate(symbols, results);
return results;
}
public static void Generate(List<string> symbols, List<string> results)
{
if (symbols.Count == 1)
{
results.Add(symbols[0]);
return;
}
for (int i = 1; i < symbols.Count; i++)
{
var left = symbols.Take(i).ToList();
var right = symbols.Skip(i).ToList();
var leftGroupings = GenerateGroupings(left);
var rightGroupings = GenerateGroupings(right);
foreach (var l in leftGroupings)
{
foreach (var r in rightGroupings)
{
string result = "(" + l + " " + r + ")";
if (!results.Contains(result))
results.Add(result);
}//foreach (var r in rightGroupings)
}//foreach (var l in leftGroupings)
}
}
}//public class TreeGroupingGenerator___CATALANING______BRACKETING_REGROUPING_COPILOTS___CARTESIAN_FOREST_CORRECTED
No comments:
Post a Comment