部活19

部活です。

リストアップした組み合わせを保存するために、まずデータ量を計算します。

C(n,r)のとき、データはr個選ばれています。そのため、C(n,r)*r個のデータが存在すると分かります。

少し脱線しますが、C(n,r)*r = C(n, n-r+1)*(n-r+1)であることを証明しておきます。

左辺 = (n! * r) / (r! * (n - r)!)

　　 = n! / ( (r - 1)! * (n - r)! ) 

右辺 = (n! * (n - r + 1) ) / ( (n - r + 1)! * (n - (n - r + 1) )! )

　　 = (n! * (n - r + 1) ) / ( (n - r + 1)! * (r - 1)! )

　　 = n!  / ( (n - r)! * (r - 1)! ) = 左辺

上記の証明から、C(n,r)*rもC(n,r)のようにある最大値を境界に値が折り返すことが分かります。

C(n,r)はnが偶数のときr = n/2、奇数のときr = (n-1)/2 または r = (n+1)/2が最大となりますから、C(n,r)*rはnが奇数のときr = (n+1)/2、偶数のときr = n/2またはr = n/2 + 1が最大となります。

前置きが長くなりましたが、C(22,r)の場合(r=1～19)のデータ量を計算すると、46,132,240となります。

値は高々22であることが知られていますので、1つの要素を1[Byte]と考えると44[MiB]、4[Byte]だと196[MiB]必要になります。しかもこれ、単純なデータ量なので扱うためには色々加工する必要があります。たとえばリスト構造化すると単純計算で更にC(22,r)*4[Byte]≒16[MiB]増えます。

22だけでこの量なので、これ以下を保存するとなると我が家のオンボロでは到底扱えない量になっているのでは？

さあ困ったぞ。