生成带有匹配括号的随机字符串

使用动态规划生成一个数据结构，该结构以递归方式知道每个选项有多少个。然后使用该数据结构查找随机选择。

我似乎是唯一一个使用这种技术的人。我总是从头开始写。但这里有一些工作代码，希望能解释它。这需要时间和类似的数据。O(length_of_string * (length_of_alphabet + 2))

import random

class DPPath:
    def __init__ (self):
        self.count = 0
        self.next = None

    def add_option(self, transition, tail):
        if self.next is None:
            self.next = {}
        self.next[transition] = tail
        self.count += tail.count

    def random (self):
        if 0 == self.count:
            return None
        else:
            return self.find(int(random.random() * self.count))

    def find (self, pos):
        result = self._find(pos)
        return "".join(reversed(result))

    def _find (self, pos):
        if self.next is None:
            return []

        for transition, tail in self.next.items():
            if pos < tail.count:
                result = tail._find(pos)
                result.append(transition)
                return result
            else:
                pos -= tail.count

        raise IndexException("find out of range")

def balanced_dp (n, alphabet):
    # Record that there is 1 empty string with balanced parens.
    base_dp = DPPath()
    base_dp.count = 1

    dps = [base_dp]

    for _ in range(n):
        # We are working backwards towards the start.
        prev_dps = [DPPath()]

        for i in range(len(dps)):
            # prev_dps needs to be bigger in case of closed paren.
            prev_dps.append(DPPath())
            # If there are closed parens, we can open one.
            if 0 < i:
                prev_dps[i-1].add_option('(', dps[i])

            # alphabet chars don't change paren balance.
            for char in alphabet:
                prev_dps[i].add_option(char, dps[i])

            # Add a closed paren.
            prev_dps[i+1].add_option(")", dps[i])

        # And we are done with this string position.
        dps = prev_dps

    # Return the one that wound up balanced.
    return dps[0]

# And a quick demo of several random strings.
for _ in range(10):
    print(balanced_dp(10, "abc").random())

仅由平衡括号组成的字符串（对于表示打开和关闭的任何任意字符对）称为“戴克字符串”，带有 p 对括号的此类字符串的数量是^{第 p 个}加泰罗尼亚数，可以计算为 （2pC p）/（p+1），如果只有 SO 允许 MathJax，这个公式会更容易阅读。如果还想允许 k 个其他非括号字符，则需要考虑，对于平衡括号对的每个数字 p ≤ n，非括号字符的不同组合数 （k（2 n-2 p）） 以及在总长度为 2 n （2 n C2 p 的字符串中插值 2 ^n-2 p 字符的方式数）).如果将 p 的每个可能值的所有这些计数相加，您将得到可能性的总宇宙的计数，然后您可以在该范围内选择一个随机数，并选择单个 p 计数对应的任何一个。然后，您可以选择随机非括号字符的随机位置。

最后，你需要得到一个均匀分布的 Dyck 字符串;一个简单的过程是将 Dyck 字符串分解为最短的平衡前缀和余数（即 ，其中 和 是平衡子序列）。为 选择一个随机长度，然后递归生成一个随机和一个随机。(A)BAB(A)AB

如果您希望生成大量随机字符串，则预先计算计数表（或记住生成计数表的函数）将产生加速。