python - 如何找到字符串的可能组合总数？

Question

如何从给定字符串中查找以特定字符 say 'a' 开头并以特定字符 say 'b' 结尾的字符串的可能子序列总数？

例子:
对于字符串 'aabb' 如果我们想知道有多少个子序列是可能的 如果子序列必须从字符 'a' 开始并以字符结束'b' 那么有效的子序列可以来自 (ab) 由索引贡献 (0,2), (ab) 由索引 (0,3), (ab) 由索引 (1,2), (ab) 由索引 (1,3), (aab) 使用索引 (0,1,2) , (aab) 使用索引 (0,1,3) ,(abb) 使用索引(0 ,2,3),(abb) 使用索引(1,2,3) 和 aabb 本身 所以总数是 9。我可以解决一个小长度的字符串，但是如何解决一个大字符串的问题，其中蛮力不起作用

Note:We consider two sub strings to be different if they start or end at different indices of the given string.

def count(str,str1 ,str2 ):
l = len(str) 
count=0
for i in range(0, l+1):
    for j in range(i+1, l+1):
        if str[i] == str1 and str[j-1] == str2:
            count+=1
return count

Answer 1

在发布我的主要代码之前，我将尝试解释它是如何工作的。让源字符串为“a123b”。有效子序列由“123”的所有子集组成，前缀为“a”，后缀为“b”。所有子集的集合称为 powerset ，itertools 文档中的代码展示了如何使用 combinations 在 Itertools Recipes 中生成幂集。部分。

# Print all subsequences of '123', prefixed with 'a' and suffixed with 'b'
from itertools import combinations

src = '123'
for i in range(len(src) + 1):
    for s in combinations(src, i):
        print('a' + ''.join(s) + 'b')

输出

ab
a1b
a2b
a3b
a12b
a13b
a23b
a123b

这是一个使用该配方的蛮力解决方案。

from itertools import combinations

def count_bruteforce(src, targets):
    c0, c1 = targets
    count = 0
    for i in range(2, len(src) + 1):
        for t in combinations(src, i):
            if t[0] == c0 and t[-1] == c1:
                count += 1
    return count

---

很容易证明the number of subsets of a set of n items is 2**n .因此，与其一个一个地生成子集，我们还可以使用该公式来加快该过程，这就是我的 count_fast 函数所做的。

from itertools import combinations

def count_bruteforce(src, targets):
    c0, c1 = targets
    count = 0
    for i in range(2, len(src) + 1):
        for t in combinations(src, i):
            if t[0] == c0 and t[-1] == c1:
                count += 1
    return count

def count_fast(src, targets):
    c0, c1 = targets
    # Find indices of the target chars
    idx = {c: [] for c in targets}
    for i, c in enumerate(src):
        if c in targets:
            idx[c].append(i)

    idx0, idx1 = idx[c0], idx[c1]
    count = 0
    for u in idx0:
        for v in idx1:
            if v < u:
                continue
            # Calculate the number of valid subsequences
            # which start at u+1 and end at v-1. 
            n = v - u - 1
            count += 2 ** n
    return count

# Test

funcs = (
    count_bruteforce,
    count_fast,
)

targets = 'ab'

data = (
    'ab', 'aabb', 'a123b', 'aacbb', 'aabbb', 
    'zababcaabb', 'aabbaaabbb',
)

for src in data:
    print(src)
    for f in funcs:
        print(f.__name__, f(src, targets))
    print()

输出

ab
count_bruteforce 1
count_fast 1

aabb
count_bruteforce 9
count_fast 9

a123b
count_bruteforce 8
count_fast 8

aacbb
count_bruteforce 18
count_fast 18

aabbb
count_bruteforce 21
count_fast 21

zababcaabb
count_bruteforce 255
count_fast 255

aabbaaabbb
count_bruteforce 730
count_fast 730

可能有一种方法可以通过在正确的位置启动内部循环而不是使用continue 来跳过不需要的索引来加快速度。