365新函数：生成有效括号-循环和递归

shaowu459

问题说明：
如()、(())、((()()))这样的括号为有效括号，特点是任意两对括号之间不交叉，且左括号和右括号总是成对出现的，一对括号总是先有左括号才有右括号。如)()、)()(这样都是无效括号。

问题一：
给定数字n（1~6），生成由n对小括号“（）”生成的所有有效组合。示例如下：

问题二：
给定数字n（1~6），生成由1~n对小括号“（）”生成的所有有效组合的并集。示例如下：

shaowu459

先来分析下问题一。

如果已经有一个小括号()，那么如何根据这个小括号来生成两个小括号的组合？我们可以通过在每个)前和字符串最后插入一对小括号()的方式来增加括号数量。
例如，在()的第一个）之前插入一对()生成：(())，在字符串最后插入一对()生成：()()。这样，在一对()的基础上通过插入一对()就生成了两对()组成的有效括号组合。
同样的方法，在两对()的所有有效组合基础上，再通过插入一对()可以获得所有3对()组成的有效括号组合：

对每个两对()的组合进行插入操作，生成6个结果，但注意其中黄色部分是重复的，最终应对操作完的结果去重处理。

shaowu459

有了上面的分析，我们可以使用REDUCE函数循环来实现在第n个)之前和字符串末尾插入一对()的目的，参考公式如下（解决此问题的公式很多，仅提供一种我做的公式做参考，下同）：

1. =UNIQUE(REDUCE("",SEQUENCE(A2),LAMBDA(x,y,TOCOL(REPLACE(x,FIND(0,SUBSTITUTE(x&0,")",0,SEQUENCE(,y))),0,"()")))))

复制代码

shaowu459

对上楼的公式简要说明如下：

=UNIQUE(     对公式生成结果去重
    REDUCE(
        "",    初始值设置为空
        SEQUENCE(A2),   A2存储n值，生成1~n的序列，循环n次
        LAMBDA(x, y,
            TOCOL(      将结果转化成1列，也即x初始值为空，后续的x都是一列
                REPLACE(      使用replace函数在第n个)前插入一对()
                    x,        对当前x中的每一个元素都进行此种插入
                    FIND(0, SUBSTITUTE(x & 0, ")", 0, SEQUENCE(, y))),   因为要在字符串末尾也插入()，因此在x后面添加1个0，并将第n个,)替换成0，使用FIND函数定位到0的位置，执行插入操作。
                    0,
                    "()"    插入值为一对()
                )
            )
        )
    )
)

shaowu459

第一个问题还可以通过递归来解决。

我们来分析一下可以插入括号的各种情况：
1）当括号字符串中的(数量大于)数量，并且(数量<n时，字符串右侧可以添加一个(或者一个)。
2）当括号字符串中的(数量大于)数量，并且(数量=n时，也就是(已用完，则右侧只能添加)。
3）当括号字符串中的(数量等于)数量，并且(数量<n时，字符串右侧只能添加(。
4）当括号字符串中的(数量等于)数量，并且(数量=n时，也就是(和)都已用完，则停止插入括号。
5）因为总是(先进入字符串，所以不存在(数量小于)数量的情况。

以下是图解说明：

shaowu459

分析完插入括号的规律，可以设置一个自定义函数：

1. =tx(r,x,y,n)

复制代码

其中r代表有效括号字符串，x代表字符串中(数量，y代表字符串中)数量，n代表总共括号对数。当使用一个(或)时，x或y就加1，直到x和y都等于n为止。

根据这种思路，定义名称tx，公式如下：

1. =LAMBDA(r,x,y,n,IF(y=n,")",IF(x<n,IF(x>y,VSTACK(tx(r&"(",x+1,y,n),tx(r&")",x,y+1,n)),r&tx("(",x+1,y,n)),r&tx(")",x,y+1,n))))

复制代码

定义名称之后，在空单元格中输入以下公式，回车：

1. =tx("",0,0,A2)

复制代码

shaowu459

对上楼公式简要说明如下：

=LAMBDA(r, x, y, n,    单元格输入tx("",0,0,A2)，r=括号组成的字符串，x=(数量，y=）数量，n=给定值
    IF(
        y = n,         设定递归退出条件，当)数量=n时，只能返回)这个字符。
        ")",
        IF(
            x < n,     如果左括号数量<n
            IF(
                x > y, 如果同时(数量大于右括号数量
                VSTACK(tx(r & "(", x + 1, y, n), tx(r & ")", x, y + 1, n)), r分别添加一个(和一个)，同时x或y加1，重新调用tx，生成结果纵向堆叠
                r & tx("(", x + 1, y, n)     如果(数量等于右括号数量，继续添加一个(
            ),
            r & tx(")", x, y + 1, n)         如果(数量等于右括号数量，只能添加一个)
        )
    )
)

shaowu459

递归公式的写法不唯一，根据退出条件的设置，同样的思路，递归公式也可以也可以写成：

1. =LAMBDA(r,x,y,n,IF(y=n,r,IF(x<n,IF(x>y,VSTACK(hx(r&"(",x+1,y,n),hx(r&")",x,y+1,n)),hx(r&"(",x+1,y,n)),hx(r&")",x,y+1,n))))

复制代码

shaowu459

接下来看第二个问题，生成1~n个括号组成的字符串的并集。

有了生成1个、2个、3个……的方法，循环1~n，直接将结果堆积在一起就成。

首先看REDUCE函数方法，将生成n个的公式稍微调整即可，两层循环，外层循环1~n，内层循环将已生成结果继续插入小括号：

1. =DROP(UNIQUE(REDUCE("",SEQUENCE(A2),LAMBDA(x,y,VSTACK(x,TOCOL(REPLACE(x,FIND(0,SUBSTITUTE(x&0,")",0,SEQUENCE(,y))),0,"()")))))),1)

复制代码

再来看递归公式方法，直接将递归公式放在REDUCE循环里即可：

1. =DROP(REDUCE(0,SEQUENCE(A2),LAMBDA(x,y,VSTACK(x,tx("",0,0,y)))),1)

复制代码

alan57

学习学习。