例如，对于 elements a,b,c,d，有 5 种可能的方式来获取相邻元素并将它们缩减为单个元素，其中必须一次组合两个元素（以下用括号表示）：
(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))
第一个示例相乘a*b，然后将该乘积乘以 ，然后将该乘积c乘以d。第二个示例首先乘以b*c，然后乘以乘积a，然后乘以乘积d。
任何 2n 个元素的有效括号表达式都必须具有 n(和 n)的属性，从左到右阅读，总是至少(有).
我知道对于 n 个数字，方式的数量是 (n-1)th Catalan number。但是如何准确地生成所有结果分组？
谢谢
（顺便说一句：这个问题有超过 160 种等效公式，所有公式都基于加泰罗尼亚数字枚举的不同组合对象。有关这些的最新列表，请参阅Richard Stanley 的加泰罗尼亚附录。）
这是 Python 中的实际代码，使用生成器来避免使用过多的内存。
#! /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
4 个元素的括号实际上不止 5 个；您实际上并不是指“括号”。你真正要问的是 N 个元素可以有多少种不同的方式reduce，或者你可以用 N 个元素制作多少棵树，同时仍然保持它们的顺序。
这对应于将表达式精确细分 N-1 次。例如，在维基百科的http://en.wikipedia.org/wiki/Catalan_number文章中的这张图表中，如果我们有 4 个元素，则正好有 5 种方法可以将二元运算符应用于它（需要正好有 3 个应用程序，因此正好有 3 个节点）：
例如，((a*b)*c)*d, (a*(b*c))*d, (a*b)*(c*d), a*((b*c)*d), a*(b*(c*d))
这是一些简洁的python代码：
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)
请注意如何grouper用此代码替换有趣的函数，例如grouper=list、 或grouper=Tree、 或grouper=...。
演示：
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')
使用递归
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
您将获得的订单如下：
n=0:
n=1: ()
n=2: []() , [()]
n=3: {}[]() , {[]}() , {[]()} , {}[()] , {[()]}
在这里，我每次都更改括号(,[,{以突出算法的工作原理。
递归将是要走的路
将 abcd 拆分为
(a) (bcd)
(ab) (cd)
(abc) (d)
这些是一些可能性
现在，您可以递归地拆分每个字符串（拆分时忽略括号）说（bcd）一种可能性
(b) (cd)
所以现在另一个组合是
((a)(b)(cd))
一旦你得到一个只有一个字母的字符串，你就可以停止递归树
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);
}
}
*
**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;
}**
*
而且，这里有一些相同的 C++ 代码：
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);
}
这是从给定的 n+1 因子生成所有可能的平衡括号字符串的 C# 版本。
注意问题的解决方案基本满足加泰罗尼亚递归关系（更多细节可以参考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();
}
在哪里
string[] CatalanNumber_GeneratingParanthesizedFactors(string s)
{
s.ThrowIfNullOrWhiteSpace("s");
if(s.Length == 1)
{
return new string[] {s};
}
var r = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
s);
return r;
}
单元测试是
[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());
}
}
最初的左括号有一个唯一匹配的右括号，这样两个括号之间的和后面的都是有效的表达式。这导致了这里用 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
在这里，我使用“a”作为左括号，使用“b”作为右括号。
catalan(0) List()
catalan(1) List(ab)
catalan(2) List(abab, aabb)
catalan(3) List(ababab, abaabb, aabbab, aababb, aaabbb)
catalan(5).size 42