python - python 中包含有限字母表上的子字符串的字符串组合

Question

假设我们有一个包含 20 个字母的字母表。另外，我们假设有以下子字符串CCAY。我想计算长度为 N 个字母并包含特定子字符串的单词数。

更准确地说，如果 N = 6，我想要以下组合 CCAYxx、xCCAYx、xxCCAY，其中 x 是字母表中的任何字母。如果 N = 7，则组合调整如下:CCAYxxx、xCCAYxx、xxCCAYx、xxxCCAY 等。

此外，我认为当子字符串仅由字母表中的一个字母组成时，例如 CCCC ，这意味着在 N = 6 的情况下，字符串 CCCCCC 应该是一个陷阱不能多次计算。

如果您能提供有关如何解决此问题的帮助或指导，我将不胜感激。 python 中的任何示例代码也将受到高度赞赏。

Answer 1

你说暴力破解是可以的，所以我们开始:

alphabet = 'abc'
substring = 'ccc'
n = 7

res = set()
for combination in itertools.product(alphabet, repeat=n-len(substring)):
    # get the carthesian product of the alphabet such that we end up 
    # with a total length of 'n' for the final combination
    for idx in range(len(combination)+1):
        res.add(''.join((*combination[:idx], substring, *combination[idx:])))
print(len(res))

打印:

295

对于没有重复的子字符串，例如 abc，我得到 396 作为结果，所以我假设它适本地覆盖了极端情况。

不用说，这效率低到足以让数学家哭泣，但只要你的问题长度很小，它就应该完成工作。

<小时/>

分析方法

最大组合数由长度n的唯一有序组合的方式给出，给定len(alphabet) = k符号，即k ^n。此外，“子字符串”可以在任意点插入到组合中，这导致总最大值为 (n+1)*k^n。后者仅在子串在任何点都不产生相同的最终组合时才成立，这使得该问题难以进行分析计算。因此，模糊的答案是您的结果将介于 k^n 和 (n+1)*k^n 之间。

如果您想计算包含子字符串的相同最终组合的数量，可以通过计算初步产品中子字符串的重复次数来实现:

n = 6
pre_prod = 'abab'
sub = 'ab'
pre_prods = ['ababab', 'aabbab', 'ababab', 'abaabb', 'ababab']
prods = ['ababab', 'aabbab', 'abaabb']
# len(pre_prodd) - pre_prod.count(sub) -> len(prods) aka 5 - 2 = 3

我会看看是否能找到一个公式......很快就会。