如何查找字符串的可能组合总数？

Question

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

例：
一个字符串'aabb'，如果我们想知道有多少子序列是可能的，如果子序列必须从性格'a'开始，以字符结束'b'那么有效的子序列可从(ab)贡献计数通过贡献的贡献的指标(1,2), (ab)索引(0,3), (ab)索引(0,2), (ab)使用使用利用索引(0,2,3),(abb)使用索引(1,2,3)和aabb本身 所以总是9 .I可以解决这个对于小长度的字符串，但如何解决索引(0,1,3) ,(abb)指数(0,1,2) , (aab)贡献的索引(1,3), (aab)这个对于一个大的字符串，其中蛮力不起作用

注：我们认为两个子串，如果他们开始有所不同，或者在给定的字符串的不同指数结束 。

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'前缀'b'和后缀'b'的所有子集组成。所有子集的集合称为powerset，而itertools文档具有的代码显示如何在Itertools Recipes部分中使用combinations来生成powerset。

# 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。因此，不是逐个生成子集，我们可以使用该公式加速该过程，这是我的功能所做的。

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跳过不必要的索引，使这个。

Answer 2

容易，这应该只是字母到两个电源的数量。即，n^2

Python实现也只是n_substrings = n ** 2