如何高效生成符合括号匹配规则的指定长度均匀随机字符串？

需求回顾 #

生成指定长度n的随机字符串，满足：

• 字符仅包含a、b、c、(、)
• 括号完全匹配（任意前缀中左括号数≥右括号数，总左括号数=右括号数）
• 所有合法字符串被选中的概率均等
• 效率优于暴力生成后筛选的方式

解决方案 #

要实现均匀采样，需分两个核心步骤：确定括号对数量，再生成对应规则的字符串。

步骤1：按概率选择括号对数量k #

首先计算每个可能的括号对数量k（k的取值范围是0 ≤ k ≤ floor(n/2)）对应的合法字符串总数：

合法数 = C(n, 2k) × C_k × 3^(n-2k)

• C(n,2k)：从n个位置中选2k个放置括号的组合数
• C_k：第k个卡特兰数（k对括号的合法序列数，公式为C_k = 1/(k+1) × C(2k, k)）
• 3^(n-2k)：剩余n-2k个位置选择a/b/c的方式数

计算所有k对应的合法数总和S，然后根据每个k的权重（合法数/S）随机选择一个k值。

步骤2：生成对应k的均匀合法字符串 #

有两种高效实现方式：

方式一：逐位动态规划概率选择

逐位构建字符串，每一步根据当前状态（已用左括号数l、已用右括号数r、已用非括号字符数m）计算可选字符的概率，随机选择后更新状态：

• 状态约束：l ≤ k、r ≤ k、m ≤ n-2k，且任意时刻l ≥ r（保证前缀括号合法）
• 可选选项及权重：
  • 非括号字符（a/b/c）：若m < n-2k，权重为3（三个字符等概率，总权重3）
  • 左括号：若l < k，权重为1
  • 右括号：若r < l且r < k，权重为1
• 选择逻辑：计算所有可选选项的总权重W，按权重比例随机选择下一个字符（比如非括号选项占3/W的概率，单括号选项占1/W的概率），然后更新对应状态。

该方法时间复杂度为O(n)，全程无回溯，直接保证均匀性。

方式二：先生成合法括号序列，再合并非括号字符

1. 生成均匀合法括号序列：
   用递归概率选择法生成k对括号的合法序列：
   • 第一个字符固定为(，然后选择匹配的)的位置：假设匹配的)在第2m+1位（m从1到k），则中间2m-2个字符是m-1对的合法序列，右侧2k-2m个字符是k-m对的合法序列。
   • 每个m对应的权重为卡特兰数乘积C_{m-1}×C_{k-m}，按此权重随机选择m，递归生成左右两部分序列后拼接，得到完整合法括号序列。
2. 合并非括号字符：
   • 从n个位置中随机选2k个位置（均匀采样组合），将生成的括号序列按顺序填入这些位置。
   • 剩余n-2k个位置，每个随机选择a/b/c中的一个。

该方法将问题拆解为两个独立的均匀采样任务，逻辑清晰，适合需要单独处理括号结构的场景。

效率优势 #

暴力筛选会生成大量非法字符串（尤其是n较大时，非法括号序列占比极高），而上述方法从根源上避免了非法候选：

• 逐位选择法每一步都严格遵守括号匹配约束，不会生成非法前缀。
• 括号序列预先生成法直接生成合法括号结构，再合并非括号字符，全程无无效输出。

内容的提问来源于stack exchange，提问作者rwallace