二進制數組的唯一子序列

Question

是否有一種計算位數組可能子序列數的有效方法？

該數組從左向右讀取，可能省略了一些元素。重複的子序列是不允許的。

當數組增長時，通過所有可能的子序列的暴力破解需要很長時間。

Answer 1

這個簡單的線性時間算法取自"Algorithms for subsequence combinatorics" by Cees Elzinga et al. (2008)，略有修改，因爲數學往往是1索引，但Python是0索引。它適用於任何序列s工作，不只是二進制序列：

def count_unique_subsequences(s): 
    """Returns the number of unique subsequences of the sequence s""" 
    L = {} 
    N = [] 
    count = 1 
    for c in s: 
     N.append(count) 
     count *= 2 
     if c in L: 
      count -= N[L[c] - 1] 
     L[c] = len(N) 
    return count 

這是一個動態編程解決方案，其迭代計算當前字符串的每個前綴的獨特子的數目。所有這些子序列仍然是下一個前綴的子序列，另外我們可以添加任何擴展下一個字符的子序列，除了那些最後一次遇到相同字符時沒有擴展的子序列。 （因爲在那一點上，我們計算了用字符擴展的所有子序列）。在該算法中，向量N保持每個連續前綴s的唯一子序列的計數（由前綴的長度索引），而L保持跟蹤每個角色最後一次出現的指數。

想到這段代碼後，我意識到N真的是多餘的;我們需要的唯一原因是能夠查找與當前字符對應的子序列計數。但是我們可以將該計數直接存儲到L而不是存儲第二個表查找的索引。這不會改變算法的時間複雜度（儘管它稍微加快了速度），但它確實將空間複雜度降低到O（| Σ |），其中Σ是字母表。對於二進制序列，它使算法成爲線性時間/恆定空間。下面是修改後的算法：

def count_unique_subsequences(s): 
    """Returns the number of unique subsequences of the sequence s""" 
    L = {} 
    count = 1 
    for c in s: 
     adds = count - L.get(c, 0) 
     L[c] = count 
     count += adds 
    return count 

至於提出的函數計算其不會出現在你的枚舉空序列，所以你可能要減一的最終結果。

在許多其他有趣的結果中，Elzinga論文還考慮了給定大小的字母表的最大獨特子序列數，表明最大數是一個廣義Fibonacci序列。對於字母大小2，最大計數可以計算爲：

max_count(0) = 1 
max_count(1) = 2 
max_count(n) = max_count(n - 2) + max_count(n - 1) + 1 

這就是fibonacci(n+2)-1。

生成最大模式的字符串由字母表的循環重複組成。

實際上枚舉所有獨特的子序列因此必須採取指數時間，因爲有（可能）指數數量的這樣的序列。但是，指數（對於二進制序列）是φ，它小於2.