Python 3で反復処理を大規模に拡張する方法

Question

コインをn回（n = 10）投げた後、2^10 = 1024の結果が出る可能性があります。 Iは、n = 10のすべての可能な結果を​​得ることが

lst = [list(i) for i in itertools.product([0, 1], repeat=n)] 

を使用し、私はコインの同じ側の最大連続配列として定義されるグループ（M）の数を知りたいです。たとえば、HHHTTHTHTHTHTの場合、この結果のグループ数は6であり、（HHH）（TT）（H）（TT）（H）（T）です。使用した10個の投げ玉の組み合わせごとのグループ数（m）は、

group=[len([len(list(grp)) for k, grp in groupby(x)]) for x in lst] 

である。最後に、私は、しかし、などの可能な組み合わせのグループの数は6（M）よりも大きい、数、

Group6=len(list(filter(lambda x:x>m,group))) 

を得る際に投げの数が増加し、例えば、（N = 200、M = 110）または（n = 500、m = 260）。私はまだPythonで上記と同じコードを使用しましたが、時間がかかり、Pythonのメモリサイズを超えていると思います。誰かが、nとmがかなり大きいとき、この問題に対処する方法を理解するのを助けてくれますか？おかげ

Answer 1

すべての可能な投げを反復処理は間違いなく大きなNのために仕事に行くのではありません（と、ここでNは私が推測する20からすでに大です）。 組み合わせ式を使用して効率的にしか計算できません。

最初に簡単な例から始めましょう：4つのトーセンスのための最小2つのグループ：私たちが2つ以上のグループをもたらすトーセンスの数を計算したい場合。

二つのグループ：：

1112 
1122 
1222 

3つのグループ：

1123 
1223 
1233 

4つのグループ：

1234 

いくつかの可能性は、（我々は 1、 2のようなグループなどに番号を付ける）があります

グループG1の値G2のものとG2のものはG3とは異なります。たった2つの値（ヘッドと尾）があるので、これは我々が最初のグループを決定した場合、我々はすべてのグループの値をdeterimedたことを意味し

G1 != G2 != G3 != ... != Gn 

：だから、と考えています。 G1が頭部である場合、すべての偶数グループはテールであり、すべての奇数グループは頭部である。

これは、上記のすべての組み合わせに対して、ちょうどの2つの構成があることを意味します。これは、ケースn=4,m=1の場合、2つの× 7 = 14の構成があることを意味します（これは、質問でプログラムを実行したときに取得するものです）。

は、今、私たちはまだ直面しなければならない唯一の問題はは、我々はこれらの超構成をカウントしようとしているかです。あなたは1を持つグループの増加と0と同じグループを記譜

：私たちは、私はアップグレード表記を呼ぶもの導入することにより、これを行うことができます。

だから1223は0101になります：2番目と4番目のインデックスでグループをアップグレードします。 1234は0111です。これはどのように役立ちますか？実際にはkグループの場合、の数とk-1のアップグレードとの組み合わせの数を数えるだけです。つまり、組み合わせ数（k-1 nCr n-1）を意味します。 n文字列の長さ（またはトスの総数）、およびkグループの数*。 Now（k-1 nCr n）は、（n-1）！/（（k-1）！*（n-k）！）として定義される。 !で階乗。 functoolsからOP として輸入事業者

すべてのkため

def ncr(n, r): 
    r = min(r, n-r) 
    if r == 0: return 1 
    return reduce(op.mul,range(n-r+1,n+1))//reduce(op.mul,range(1,r+1)) 

そして今、最後のステップは唯一組み合わせの数を計算することである（2倍）を低減インポート：私はhereからnCrを計算する方法を借りmからnまでです。だから、：

def group_num(n,m): 
    total = 0 
    for i in range(m+1,n+1): 
     total += ncr(n-1,i-1) 
    return 2*total 

またはワンライナーに入れる：

def group_num(n,m): 
    return 2*sum(ncr(n-1,i-1) for i in range(m+1,n+1)) 

今、私たちは私たちのコードをテストすることができます

（最初の2のための）期待される番号です

>>> group_num(4,1) 
14 
>>> group_num(10,6) 
260 
>>> group_num(200,110) 
125409844583698900384745448848066934911164089598228258053888 
>>> group_num(500,260) 
606609270097725645141493459934317664675833205307408583743573981944035656294544972476175251556943050783856517254296239386495518290119646417132819099088 

。あなたが見ることができるように、トータル量が膨大になるので、一度に1つのトグをカウントする最速のアルゴリズムでさえも、このアプローチによって簡単にパフォーマンスが向上します（結果は1秒未満で計算されます）。

ncr関数は、O（n）で計算できます（ただし、階乗のメモを使用することによっても改善できます）。したがって、group_num関数は、O（（n-m）× n）に計算されます（メモの最適化なし）。このように、指数関数的な振る舞いを完全に排除する。