我需要生成一个一定长度的随机字符串——为了便于论证，假设是十个字符——由字符a,b,c,(,)组成，规则是必须匹配括号。
例如aaaaaaaaaa,abba()abba和((((()))))是有效的字符串，但)aaaabbbb(不是。
什么算法会产生一个随机字符串，从所有符合这些规则的字符串集合中均匀抽样?(并且比"继续生成字符串而不考虑平衡规则，丢弃失败的字符串"运行得更快，这可能最终在找到有效字符串之前生成很多无效字符串。)
仅由平衡括号组成的字符串(对于任何表示开和闭的任意字符对)称为" Dyck字符串"，这种带有p对括号的字符串的数目是p加泰罗尼亚数，可计算为(2pC)p)/(p+1)，如果只允许MathJax，这个公式将更容易阅读。如果你还想允许k其他非括号字符，你需要考虑，对于每一对平衡括号的数字p≤n，非括号字符的不同组合(k(2n-2p))的数量，以及在一个总长度为2n(2nC)的字符串中插入2n-2p字符的方法的数量。2p)。如果将p的每个可能值的所有这些计数相加，您将得到整个可能性的计数，然后您可以在该范围内选择一个随机数，并选择单个p计数中对应的任何一个。然后您可以选择随机的非括号字符的随机位置。
最后，你需要得到一个均匀分布的Dyck字符串;一个简单的过程是将Dyck字符串分解为它的最短平衡前缀和余数(即(A)B，其中A和B是平衡子序列)。为(A)选择一个随机长度，然后递归生成一个随机A和一个随机B。
如果你希望生成大量随机字符串，那么预先计算计数表(或记忆生成计数表的函数)将会提高速度。
使用动态编程来生成一个数据结构,知道有多少对于每一个选择,递归。然后使用该数据结构找到一个随机选择。
我似乎是唯一使用这种技术的人。我总是从零开始写。但这里是工作代码，希望能解释它。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())