如何确定包含简并子字符串的可能字母组合的数量

Question

我已经绞尽脑汁待了几天,研究出一系列或封闭形式的等式来解决以下问题:

具体来说:给定长度为N的所有字符串,从L字母的字母表中开始(以'A'开头,例如{A,B},{A,B,C},...),这些字符串中有多少包含与模式匹配的子字符串:'A',超过1不 - 'A','A'.该模式的标准正则表达式将是A[^A][^A]+A.

可能的串的数量是很简单的:L ^Ñ.对于N和L的小值,简单地创建所有可能的组合并使用正则表达式来查找与模式匹配的子串也是非常实用的.在R:

all.combinations <- function(N, L) {
    apply(
        expand.grid(rep(list(LETTERS[1:L]), N)),
        1,
        paste,
        collapse = ''
    )
}

matching.pattern <- function(N, L, pattern = 'A[^A][^A]+A') {
    sum(grepl(pattern, all.combinations(N, L)))
}

all.combinations(4, 2)
matching.pattern(4, 2)

我想出了以下内容,适用于N <7:

M <- function(N, L) {
    sum(
        sapply(
            2:(N-2),
            function(g) {
                (N - g - 1) * (L - 1) ** g * L ** (N - g - 2)
            }
        )
    )
}

不幸的是,这仅在N <7时起作用,因为它只是添加了具有子串A..A,A ... A,A ...... A等的组合,并且一些组合显然具有多个匹配的子串(例如,A ..A..A,A..A ... A),计算两次.

有什么建议？我也对程序解决方案持开放态度,只要它们不会因组合数量而爆炸(就像我上面的代码那样).我希望能够计算N的值从15到25,L从2到10.

对于它的价值,这里是N和L的某些值的组合数量和匹配组合,通过生成所有组合并进行正则表达式匹配来确定:

 N  L  combinations  matching
--  -  ------------  --------
 4  2            16         1
 5  2            32         5
 6  2            64        17
 7  2           128        48
 8  2           256       122
 9  2           512       290
10  2          1024       659
 4  3            81         4
 5  3           243        32
 6  3           729       172
 7  3          2187       760
 8  3          6561      2996
 9  3         19683     10960
10  3         59049     38076
 4  4           256         9
 5  4          1024        99
 6  4          4096       729
 7  4         16384      4410
 8  4         65536     23778
 9  4        262144    118854
10  4       1048576    563499

Answer 1

可以使用动态规划方法。

对于固定L，令为包含给定模式的X(n)长度字符串的数量，令为包含给定模式且以 A 开头的长度字符串的数量。nA(n)n

首先推导 的递推公式A(n)。A(n)让我们通过按前 2-3 个字母分组来计算所有字符串。with中的字符串数量A(n)：

• “第二个字母A”是A(n-1)，
• “第二个字母非 A，第三个字母是 A”是A(n-2)，
• “第二个和第三个字母非 A”是(L^(n-3) - (L-1)^(n-3))。这是因为字符串“需要”剩余字母中至少有一个 A 才能被计数。

接着就，随即：

A(n) = A(n-1) + (L-1) * (A(n-2) + (L-1) * (L^(n-3) - (L-1)^(n-3)))

长度字符串n+1可以以 A 或非 A 开头：

X(n+1) = A(n+1) + (L-1) * X(n)
X(i) = A(i) = 0, for i <= 3

Python实现：

def combs(l, n):
    x = [0] * (n + 1)  # First element is not used, easier indexing
    a = [0] * (n + 1)
    for i in range(4, n+1):
        a[i] = a[i-1] + (l-1) * (a[i-2] + (l-1) * (l**(i-3) - (l-1)**(i-3)))
        x[i] = a[i] + (l-1) * x[i-1]
    return x[4:]

print(combs(2, 10))
print(combs(3, 10))
print(combs(4, 10))