论坛 › 编程擂台 › 不允许出现连续相同符号的括号序列

KeyTo9_Fans 发表于 2023-2-14 16:45:45

不允许出现连续相同符号的括号序列

以 “（” 和 “）” 这两种符号构成的、长度为 2n 的合法的括号序列，

我们已经知道是有卡特兰(n) 种，其中

卡特兰(n) = (2n)!/(n!)^2/(n+1)

我现在想把这个问题扩展一下，要求括号序列里不得出现连续k个 “（”、也不得出现连续k个 “）”，

给定 n 和 k，问长度为 2n 的、不出现 k 个连续相同符号的括号序列有多少种？

这是一个二维数列，OEIS称之为“Table”，

我们求出来之后，看看OEIS收录了这个“Table”没有，

如果有，我们向他学习，了解更多相关知识；

如果没有，我们把这个新的“Table”贡献给他。

northwolves 发表于 2023-2-15 15:41:49

(1, 1, )
(2, 2, )
(3, 5, )
(4, 14, )
(5, 42, )
(6, 132, )
(7, 429, )
(8, 1430, )
(9, 4862, )
(10, 16796, )
(11, 58786, )
(12, 208012, )

mathe 发表于 2023-2-15 17:14:50

我们假设长度为2n连续同向括号数目小于k的序列数目为f(k-1,n)
于是我们知道对于k>n+1,必然有f(k,n)=f(k-1,n), 而且f(1,n)=1 (只能左右括号交替),而且记f(k,0)=1.
我们分析f(k,n)的情况,也就是2n个符号，连续括号数目不超过k+1的计数情况
第一个位置必然在左括号，我们分析和这个位置匹配的右括号位置必然在某个偶数位置，如果这个位置为2s
那么1~2s之间我们去掉第一个位置的左括号和第2s位置的右括号，得到一个长度为2(s-1),所有连续括号数目小于k的序列，所以数目为f(k-1,s-1), 而余下2n-2s个数匹配方案数目为f(k,n-s).
于是我们得到递归公式$f(k,n)=\sum_{s=1}^n f(k-1,s-1)f(k,n-s)$。 这个算法复杂度$O(n^3)$很容易计算到n较大的情况
计算得到
? getn(2)
%3 =
? getn(3)
%4 =
? getn(4)
%5 =
? getn(5)
%6 =
? getn(6)
%7 =
? getn(7)
%8 =
? getn(8)
%9 =
? getn(9)
%10 =
? getn(10)
%11 =
? getn(11)
%12 =
? getn(12)
%13 =
? getn(13)
%14 =
? getn(14)
%15 =
对应第三列 A001519 , 第四列 A007051， 第五列 A080937等
northwolves n=5 k=3时为17，我的16应该是他包含了有括号连续k个情况如(()(()()))

northwolves 发表于 2023-2-15 17:55:39

本帖最后由 northwolves 于 2023-2-15 19:58 编辑

n=3, 5, ['((()))', '(()())', '(())()', '()(())', '()()()']
k=1, 0, []]
k=2, 1, ['()()()']
k=3, 4, ['(()())', '(())()', '()(())', '()()()']

n=4, 14, ['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']
k=1, 0, []]
k=2, 1, ['()()()()']
k=3, 8, ['(()()())', '(()())()', '(())(())', '(())()()', '()(()())', '()(())()', '()()(())', '()()()()']
k=4, 13, ['((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']

n=5, 42, ['((((()))))', '(((()())))', '(((())()))', '(((()))())', '(((())))()', '((()(())))', '((()()()))', '((()())())', '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()((())))', '(()(()()))', '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())((()))', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(((())))', '()((()()))', '()((())())', '()((()))()', '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()', '()()()(())', '()()()()()']
k=1, 0, []]
k=2, 1, ['()()()()()']
k=3, 17, ['(()(())())', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()(()())', '()()(())()', '()()()(())', '()()()()()']
k=4, 34, ['((()()()))', '((()())())', '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()(()()))', '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())((()))', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()((()()))', '()((())())', '()((()))()', '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()', '()()()(())', '()()()()()']
k=5, 41, ['(((()())))', '(((())()))', '(((()))())', '(((())))()', '((()(())))', '((()()()))', '((()())())', '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()((())))', '(()(()()))', '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())((()))', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(((())))', '()((()()))', '()((())())', '()((()))()', '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()', '()()()(())', '()()()()()']

northwolves 发表于 2023-2-15 17:58:36

def kuohao(n,l,r,s,t):
    if(l == n and r == n):
      t.append(s)
      return
    if(l < n):
      kuohao(n, l+1, r, s+"(", t)
    if(r < l):
      kuohao(n, l, r + 1, s+")", t)
# def diag(n):
#   x,y=[],[]
#   kuohao(n, 0, 0, "", x)
#   for k in range(1,n+1):
#         a,b=('('*k,')'*k)
#         t=
#         y.append(len(t))
#   return(n,len(x),y)

def diag(n):
    x,y=[],[]
    kuohao(n, 0, 0, "", x)
    y.append(['n='+str(n),len(x),x])
    for k in range(1,n+1):
      a,b=('('*k,')'*k)
      t=
      y.append(['k='+str(k),len(t),t])
    return(y)

for n in range(3,6):
    y=diag(n)
    for k in range(n+1):
      print(y)

northwolves 发表于 2023-2-15 18:00:03

字符串比较的穷举硬算，速度实在不怎么样

mathe 发表于 2023-2-15 19:58:21

我弄错了，我这个计算的是嵌套深度小于k的数目，而不是连续符号不超过k的数目。
计算连续符号小于k的数目，我们也可以采用动态规划来做。
我们想像建立一个坐标轴，从原点出发，每遇到一个(, 那么向右上方移动一格（长度$\sqrt{2}$，每次遇到一个),那么向右下方移动一格。遍历2n个符号以后，必然到达坐标(2n,0). 而在这个遍历过程中，每次连续上升或连续下降的线段长度都小于$\sqrt{2}k$,而且移动过程永远不会跑到横坐标下方。
我们采用动态规划计算从原点出发，在某个上升线段终点到达点(x,y)的不同方案数目为A(k,x,y), 在某个下降线段终点到达点(x,y)的不同方案数目为B(k,x,y). 其中$0\le y\le x$.
于是B(k,0,0)=1, A(k,0,0)=0,而且y<0时$A(k,x,y)=B(k,x,y)=0$。当$y>x, A(k,x,y)=B(k,x,y)=0$
于是$A(k,x,y)=\sum_{h=1}^{k-1} B(k,x-h,y-h), B(k,x,y) = \sum_{h=1}^{k-1} A(k,x-h,y+h)$
于是$B(k,2n,0)$就是我们要求的结果。
#include <iostream>
#include <gmpxx.h>

#define MAXN 100
#define K 3
mpz_class A;
mpz_class B;

void init()
{
        B=1;
        A=0;
}

int main()
{
        int x,y,h;
        init();
        for(x=1;x<=2*MAXN;x++){
                for(y=0;y<=x;y++){
                        mpz_class r=0;
                        for(h=1;h<K;h++){
                                if(x-h>=0&&y-h>=0){
                                        r+=B;
                                }
                        }
                        A=r;
                        r=0;
                        for(h=1;h<K;h++){
                                if(x-h>=0&&y+h<=x-h){
                                        r+=A;
                                }
                        }
                        B=r;
                }
        }
        for(x=1;x<=MAXN;x++){
                std::cout<<"count "<<x<<"="<<B<<std::endl;
        }
        return 0;

}

比如k=3对应的结果如下:
count 1=1
count 2=2
count 3=4
count 4=8
count 5=17
count 6=37
count 7=82
count 8=185
count 9=423
count 10=978
count 11=2283
count 12=5373
count 13=12735
count 14=30372
count 15=72832
count 16=175502
count 17=424748
count 18=1032004
count 19=2516347
count 20=6155441
count 21=15101701
count 22=37150472
count 23=91618049
count 24=226460893
count 25=560954047
count 26=1392251012
count 27=3461824644
count 28=8622571758
count 29=21511212261
count 30=53745962199
count 31=134474581374
count 32=336908488839
count 33=845139060165
count 34=2122553644686
count 35=5336735929371
count 36=13432403613621
count 37=33843022209066
count 38=85349327734485
count 39=215440028338359
count 40=544288586926914
count 41=1376230297675914
count 42=3482537223611046
count 43=8819175375714063
count 44=22349794473772659
count 45=56678600914995057
count 46=143830921235537742
count 47=365225623668676437
count 48=927972354829010775
count 49=2359192024476568203
count 50=6001174121892988758
count 51=15273713134056377698
count 52=38893747432145085266
count 53=99090832134641995427
count 54=252579381177903040849
count 55=644118340220292169786
count 56=1643348924746923013481
count 57=4194532932723720267271
count 58=10710773165730370402070
count 59=27361217667381195152609
count 60=69923263927774760117419
count 61=178761583832906815958299
count 62=457180542019634361749654
count 63=1169653910683020997823700
count 64=2993493968182857335738916
count 65=7663836950023084292126586
count 66=19627124209913879819201256
count 67=50281185027971273570344779
count 68=128851301008215990676245297
count 69=330295607482296149639113771
count 70=846922848867278127081934118
count 71=2172243398314031502060434813
count 72=5573055540747246795936497203
count 73=14301951559375317288722742625
count 74=36712267090479571354186761752
count 75=94262318866766131085885820862
count 76=242087967735412291153757221292
count 77=621890217530867044998372625244
count 78=1597927417599990976164331285618
count 79=4106772441264045401019924649921
count 80=10557037252659735639822884541089
count 81=27144318295978988020876731613899
count 82=69808615378820015816460193046634
count 83=179568484819409906464233459965565
count 84=461998012612770916903282585499931
count 85=1188877068859680412470053314034196
count 86=3059980617900905437254279674385261
count 87=7877408686568953921404087246339411
count 88=20282861001228149602530202549462410
count 89=52234134723235412099021791134645474
count 90=134541797507827311283829108795938674
count 91=346605946314513254492433135097630809
count 92=893077485129793636878895057273178901
count 93=2301521609537728551186835553085928773
count 94=5932151623905973421624468114595077244
count 95=15292526112023196667544094397358322057
count 96=39428894200253097844359818441341768857
count 97=101675651191856047918093722573856681533
count 98=262231577763896699071580185616362344474
count 99=676421455498354043694557131153096948242
count 100=1745070036795404191515676477125772132266
对应https://oeis.org/A004148

northwolves 发表于 2023-2-15 22:39:59

k=4, https://oeis.org/A186236

查看完整版本: 不允许出现连续相同符号的括号序列