本文共 4555 字，大约阅读时间需要 15 分钟。
JAVA算法：括号配对问题与卡塔兰数（Catalan number）
LeetCode中第22题目：22. Generate Parentheses
原题链接：
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))", "(()())", "(())()", "()(())", "()()()" ]这道题目大意是：给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
问题分析
求解这个题目并不是很困难。但是要深究这个题目，需要了解什么是卡塔兰数，又可以叫做卡特兰数，英文是：Catalan Number。
那么什么是Catalan Number？
百度百科给出的描述为：卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 （1814–1894）的名字来命名。
其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
下面是一些典型的问题：（实质上都是递推等式的应用）
- 括号化：矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
- 出栈次序：一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
- n对括号正确匹配数目。
给定n对括号，求括号正确配对的字符串数，例如：
0对括号：[空序列]—— 1种可能
1对括号：() —— 1种可能
2对括号：()() (()) —— 2种可能
3对括号：((())) ()(()) ()()() (())() (()()) —— 5种可能
那么问题来了，n对括号有多少种正确配对的可能呢？
考虑n对括号时的任意一种配对方案，最后一个右括号有唯一的与之匹配的左括号，于是有唯一的表示A(B)，其中A和B也是合法的括号匹配序列。
假设S(n)为n对括号的正确配对数目，那么有递推关系S(n)=S(0)S(n-1)+S(1)S(n-2) +...+S(n-1)S(0)，显然S(n)是卡特兰数。
算法设计
使用递归算法求解前20个Catalan Number
package com.bean.algorithm.basic;public class CatalanNumbers2 { // 求卡特兰数 // 使用递归的方式解决卡特兰数 public static long CatalanNumber(int n) { if (n == 1) { return 1; } else { return CatalanNumber(n - 1) * 2 * (2 * n - 1) / (n + 1); } } public static void main(String[] args) { //为了防止计算溢出，求前20个Catalan Number for (int i = 1; i <= 20; i++) { System.out.println(i + "'s Catalan Number is " + CatalanNumber(i)); } }} 程序运行结果为：
1's Catalan Number is 1
2's Catalan Number is 2 3's Catalan Number is 5 4's Catalan Number is 14 5's Catalan Number is 42 6's Catalan Number is 132 7's Catalan Number is 429 8's Catalan Number is 1430 9's Catalan Number is 4862 10's Catalan Number is 16796 11's Catalan Number is 58786 12's Catalan Number is 208012 13's Catalan Number is 742900 14's Catalan Number is 2674440 15's Catalan Number is 9694845 16's Catalan Number is 35357670 17's Catalan Number is 129644790 18's Catalan Number is 477638700 19's Catalan Number is 1767263190 20's Catalan Number is 6564120420另外一种解法：
package com.bean.algorithm.basic;import java.util.*;import java.math.BigInteger;public class CatalanNumbers { // 求卡特兰数 public static void main(String[] args) { int numberOfCatalan = 101; // 要求多少个卡特兰数 BigInteger[] digis = new BigInteger[numberOfCatalan]; digis = generateCatalan(numberOfCatalan); System.out.println("请输入需要求解第几个Catalan Number:"); Scanner scanner = new Scanner(System.in); int number; while (true) { number = scanner.nextInt(); if (number == -1) break; String answer = digis[number].toString(); System.out.println(answer); } } static BigInteger[] generateCatalan(int numberOfCatalan) { // 产生卡特兰数 BigInteger digis[] = new BigInteger[numberOfCatalan + 1]; BigInteger x = new BigInteger("1"); // 第一个卡特兰数为1 digis[1] = x; int y = 0; int z = 0; for (int counter = 2; counter <= numberOfCatalan; ++counter) { y = 4 * counter - 2; z = counter + 1; digis[counter] = digis[counter - 1].multiply(new BigInteger("" + y)); digis[counter] = digis[counter].divide(new BigInteger("" + z)); } return digis; }} 程序运行结果：
请输入需要求解第几个Catalan Number:
5 42LeetCode第 20 题 的解法：
采用DFS算法求解：
package com.bean.algorithmbasic;import java.util.Iterator;import java.util.LinkedList;import java.util.List;public class GenerateParenthesesDemo { public List generateParenthesis(int n) { List result = new LinkedList (); if (n > 0) dfs("", n, n, result); return result; } /* * DFS算法设计 * */ private void dfs(String prefix, int left, int right, List result) { if (left == 0 && right == 0) result.add(prefix); // Has left Parenthesis if (left > 0) dfs(prefix + '(', left - 1, right, result); // has more right Parenthesis if (left < right) dfs(prefix + ')', left, right - 1, result); } public static void main(String[] args) { // TODO Auto-generated method stub int n = 4; GenerateParenthesesDemo gpd = new GenerateParenthesesDemo(); List list = gpd.generateParenthesis(n); Iterator itx = list.iterator(); while (itx.hasNext()) { String str = itx.next(); System.out.println(str); } System.out.println("有 "+list.size()+" 种配对方案..."); }} 程序运行结果：
(((())))
((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() 有 14 种配对方案...
转载地址：http://jntdi.baihongyu.com/