algorithm - 有效括号数

Question

我必须找出有效括号的数量。括号有两种类型[] ,()。有多少种方法可以使用 X 和 Y 的数量来构造一个有效的序列[] ,()。对于这个问题，我们认为([])是无效的方式，即() can't hold []. 有没有比递归更好的解决方案。

For Example X=1 and Y=1
[]()
()[]
[()]

Answer 1

因为方括号不能在圆括号内，所以在每次出现方括号之前，每个圆括号序列都必须是完整的（即，开括号减去右括号的数量倒为零）。

  1      012    1      0  
()[(())()][[()()]((()))]()
10 121010   1010 123210 10

这实际上意味着方括号将圆括号拆分为单独的独立序列：

   1   0   1   2   1   0
...[...]...[...[...]...]...

其中完整的圆括号序列可以放在方括号之间的任何位置。

正如 Paul Hankin 所提到的，只有一种括号的有效序列数由Catalan Number给出。这为您提供了方括号的有效序列数，以及要插入方括号之间某处的任意数量的圆括号的有效序列数。

不幸的是，找出圆括号可以通过何种方式分布到方括号之间的不同位置是一个分区问题，解决这个问题的逻辑方法是递归。因此，这种思路可能会导致一种算法，但不会导致一种避免递归的算法。

但是，查找分区所需的递归数远小于加泰罗尼亚数（例如 20 有 627 个分区，但 20 的加泰罗尼亚数是 6,564,120,420），因此这种方法比递归枚举每个有效序列要快得多。

---

这是一个简单的示例来演示它是如何工作的：

X=2, Y=3

方括号的有效序列：

加泰罗尼亚语数(2) = 2

1. [ ] [ ]  
2. [ [ ] ]

圆括号的位置：

2 × X + 1 = 5

1[2]3[4]5
1[2[3]4]5

圆括号的分区：

p(Y) = 3

3
2,1
1,1,1

分区排列：

分区：3（部分数量：1）
→ 5 = 5

3,0,0,0,0  0,3,0,0,0  0,0,3,0,0  0,0,0,3,0  0,0,0,0,3  

分区：2,1（部分数：2）
→ 5 × 4 = 20

2,1,0,0,0  2,0,1,0,0  2,0,0,1,0  2,0,0,0,1  
1,2,0,0,0  0,2,1,0,0  0,2,0,1,0  0,2,0,0,1  
1,0,2,0,0  0,1,2,0,0  0,0,2,1,0  0,0,2,0,1  
1,0,0,2,0  0,1,0,2,0  0,0,1,2,0  0,0,0,2,1  
1,0,0,0,2  0,1,0,0,2  0,0,1,0,2  0,0,0,1,2  

分区：1,1,1（零件数：3，相同：3）
→（5×4×3）/（1×2×3）= 10

1,1,1,0,0  1,1,0,1,0  1,1,0,0,1  
1,0,1,1,0  1,0,1,0,1  1,0,0,1,1  
0,1,1,1,0  0,1,1,0,1  0,1,0,1,1  0,0,1,1,1  

圆括号的有效序列：

加泰罗尼亚语数(3) = 5

1. ()()()
2. ()(())
3. (())()
4. (()())
5. ((()))

加泰罗尼亚语数(2) = 2

1. ()()
2. (())

加泰罗尼亚语数(1) = 1

1. ()

加泰罗尼亚语数(0) = 1

1. 

每个分区的有效序列：

3,0,0,0,0  5 x 1 x 1 x 1 x 1  =  5
2,1,0,0,0  2 x 1 x 1 x 1 x 1  =  2
1,1,1,0,0  1 x 1 x 1 x 1 x 1  =  1

有效序列总数：

方括号：2 圆括号
：75

 5 x 5 = 25  
20 x 2 = 40  
10 x 1 = 10  

总计：2 × 75 = 150

Answer 2

对于分组的自封闭圆括号和方括号的给定排列的任何给定组合，我们可以使用多集组合来确定排列的数量：

n + k - 1 choose k, where k is the smaller of the number of self-enclosed parenthetical groups and the total number of square brackets, and n is the larger of the two + 1.

方括号的排列数是第n个加泰罗尼亚数。

生成括号组的一种方法是分配越来越多的组，并计算（X - 分配的组数）的每个分区的不同排列的数量乘以parts-as-nth-Catalan的总和。例如：

X = 4
Counts for each grouping:

1 group: Cat 3
2 groups: Cat 2 * 2 + 1 // partitions [2,0] * 2 and [1,1]
3 groups: 3 // partition [1,0,0] * 3
4 groups: 1 // partition [0,0,0,0]

我还没有想出避免分区的方法，并且有兴趣学习。