バイナリ配列のユニークなサブシーケンス

Question

ビット配列の可能なサブシーケンス数を効率的に計算する方法はありますか？

配列は左から右に読み取られ、おそらくいくつかの要素が省略されます。重複した部分列は許可されません。

配列のサイズが大きくなると、すべての可能なサブシーケンスをブルートフォースするのに時間がかかります。

Answer 1

この単純な線形時間アルゴリズムは"Algorithms for subsequence combinatorics" by Cees Elzinga et al. (2008)から得られます。数学は1インデックス化される傾向がありますが、Pythonは0インデックス化される傾向があります。これは、反復的に現在の文字列の各プレフィックスのユニークサブ配列の数を計算し、動的プログラミングソリューション、ある

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 

：それは、任意の順序sのためだけではなく、バイナリシーケンスを動作します。これらのサブシーケンスはすべて次のプレフィックスのサブシーケンスです。さらに、最後に同じ文字に遭遇したときに拡張されなかったサブシーケンスを除いて、次の文字で拡張されたサブシーケンスを追加できます。このアルゴリズムでは、ベクトルNは、s（接頭辞の長さで索引付けされている）の連続する接頭辞ごとに一意の部分配列の数を維持し、Lは追跡します各文字の最後の出現のインデックスの

このコードについて考えると、Nは実際には冗長であることに気付きました。私たちが必要とする唯一の理由は、現在の文字に対応する部分列数を検索できることです。しかし、2番目のテーブルルックアップのインデックスを格納するのではなく、そのカウントを直接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 

は、機能を使用すると、最終的な結果から1を減算する場合がありますので、あなたの列挙に表示されていない空のシーケンスをカウントします。

他の多くの興味深い結果の中で、Elzingaの論文では、与えられたサイズのアルファベットの一意の最大サブシーケンス数も考慮して、最大カウントが一般化されたフィボナッチシーケンスであることを示しています。アルファベットサイズ2の場合、最大カウントは、fibonacci(n+2)-1であり、

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

のように計算できます。

最大パターンを生成する文字列は、アルファベットの巡回繰り返しで構成されます。

実際には、指数関数的な数のシーケンスが存在するため、すべてのユニークなサブシーケンスを列挙するには指数関数的な時間を要する必要があります。ただし、指数（バイナリシーケンスの場合）はφであり、2未満です。