文字列の可能な組み合わせの合計数を調べる方法は？

Question

特定の文字で始まる文字列の可能なサブシーケンスの合計数を調べる方法 'a'と特定の文字で終了すると指定された文字列の'b'と言いますか？

例：文字列'aabb'ため
我々は、サブシーケンスはサブシーケンスは文字'a'から始まり、文字'b'で終わらなければならないならば、有効なサブ配列は貢献(ab)から得ることができる可能ですどのように多くの数を知りたい場合はインデックス(1,2,3)とaabb自体 そう総使用指標(0,2,3),(abb)を使用して索引(0,1,3) ,(abb)を使用して索引(0,1,2) , (aab)を使用して索引(1,3), (aab)によって寄与率(1,2), (ab)によって寄与率(0,3), (ab)によって寄与率(0,2), (ab) 9 .Iが小さい長さの文字列のためにこれを解決することができるが、解決する方法であることによりこのブルートフォースは

注動作しない大きな文字列のために：我々は、彼らが開始する場合異なることや、指定された文字列の異なる指標で を終了するために、2つのサブ文字列を考えます。

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'の接頭辞で構成されるすべてのサブセットで構成されます。すべてのサブセットのセットは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ことを示すことができます。したがって、サブセットを1つずつ作成するのではなく、私の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を使用してこれを作るための方法も。

Answer 2

簡単に、それはちょうど2つのパワーへの手紙の数でなければなりません。すなわちは、n^2

Python実装はちょうど私が私のメインのコードを投稿する前に、私はそれがどのように動作するかを説明しようとするでしょうn_substrings = n ** 2