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))

打印：

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

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

分析方法

最大组合数由长度n的唯一有序组合方式给出，给定len(alphabet) = k个符号，即k^n。此外，'substring' 可以在任意点插入组合，这导致总最大值为 (n+1)*k^n。后者仅在子字符串在任何时候不产生相同的最终组合时才成立，这使得这个问题难以分析计算。所以，模糊的答案是 your result will be somewhere between k^n and (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

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

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

string combinations that include a substring over a finite alphabet in python

python

string

combinations

combinatorics

python-3.x

分析方法