組み合わせの計算、その2 (35個の中から選ぶ組み合わせ)

f:id:araemonz:20190609142247j:plain
Capacitance Decade Box

これは現在制作中のCapacitance Decade Box だ。スイッチが35個ある。コンデンサを並列に繋げば容量を足し算で合成できるため、様々な容量を作り出すことができる。それでは一体、どれほどのパターンを作り出すことができるのだろうか?前回作った組み合わせの計算関数 combinationを使って、この35個のスイッチの組み合わせが何通りあるかを計算してみた。

n = 35
total = 0

for r in range(1, n+1):
    res = combination(n, r)
    print("{n}C{r} = {res}".format(
        n=n,
        r=r,
        res=res))
    total += res

print("合計:", total)

出力結果はこちら。

35C1 = 35
35C2 = 595
35C3 = 6545
35C4 = 52360
35C5 = 324632
35C6 = 1623160
35C7 = 6724520
35C8 = 23535820
35C9 = 70607460
35C10 = 183579396
35C11 = 417225900
35C12 = 834451800
35C13 = 1476337800
35C14 = 2319959400
35C15 = 3247943160
35C16 = 4059928950
35C17 = 4537567650
35C18 = 4537567650
35C19 = 4059928950
35C20 = 3247943160
35C21 = 2319959400
35C22 = 1476337800
35C23 = 834451800
35C24 = 417225900
35C25 = 183579396
35C26 = 70607460
35C27 = 23535820
35C28 = 6724520
35C29 = 1623160
35C30 = 324632
35C31 = 52360
35C32 = 6545
35C33 = 595
35C34 = 35
35C35 = 1
合計: 34359738367

ななななんと、343億通りあることが分かった。もちろん順列ではない。組み合わせだ。だから並び順が違くても同じものとして見なされるため数には入っていない。計算間違いじゃないのかと疑ったほどだが、どうも本当らしい。

組み合わせを配列で返してくれるファンクションも作ってみたので載せておく。

def nCr(s1, r):  # ただしmは、1 <= m <= len(s1) の範囲とする

    a = s1[0]  # 配列の最初の値を対象する
    # a と組み合わせられる値は aを以外の配列を対象とすれば良い
    s2 = s1[1:]  # => [2, 3, 4, 5]

    res = []
    if r == 1:  # 例外ケースとして処理
        for a in s1:
            res.append(a)
        return res

    elif r == 2:
        for b in s2:
            res.append([a, b])
    else:
        for bc in nCr(s2, r-1):
            # bc.insert(0, a)
            bc.append(a)
            res.append(bc)

    if len(s1) > r - 1:
        return res + nCr(s2, r)
    else:
        return []

あとから知ったのだがPythonには itertools.combinations という組み合わせを計算できるファンクションがあらかじめ用意されていたorz。 私が作ったプログラミングは多少スペックは落ちる。しかし本家とアルゴリズム的にそんなに差はなさそうだった。配列処理がボトルネックのようだ。35C17なんて40億を超える配列を処理しなければならない。そして思ったのだが、nCrは再帰処理なのでキャッシュを使ったらかなり速度改善ではかろうか?

さておき、コンデンサー の容量の大きいものと小さいものを組み合わせることは現実的必要ないのではなかろうか。抵抗と違ってコンデンサーの容量誤差は大きい。5%〜20%なんてものが存在する。つまり誤差を考えた上での回路設計にっているのだから1μFに100pFを足すなどのケースは省いて良いといえる。

そういうことで、これ以上の探求は時間もかかるし馬鹿馬鹿しいのでやめておこうか。

と言いつつ、先ほどのプログラムのキャッシュ版もつくってしまった。

cache = {}


def join(a):
    s = ""
    for b in a:
        s += str(b) + "_"
    return s


def nCr(s1, r):  # ただしmは、1 <= m <= len(s1) の範囲とする

    a = s1[0]  # 配列の最初の値を対象する
    # a と組み合わせられる値は aを以外の配列を対象とすれば良い
    s2 = s1[1:]  # => [2, 3, 4, 5]

    res = []
    if r == 1:  # 例外ケースとして処理
        for a in s1:
            res.append(a)
        return res

    elif r == 2:
        for b in s2:
            res.append([a, b])
    else:
        for bc in nCr(s2, r-1):
            # bc.insert(0, a)
            bc.append(a)
            res.append(bc)

    if len(s1) > r - 1:
        prefix = join(s2)
        key = "{prefix}{n}C{r}".format(prefix=prefix, n=len(s2), r=r)

        if cache.get(key) is None:
            cache[key] = nCr(s2, r)

        return res + cache[key]
    else:
        return []

キャッシュを利用すると速い。なかなか悪くない結果が得られたのでベンチマークをとってみた。 35C1から35C9までを計算した結果である。キャッシュの差がじわじわ効いている。

itertools.combinations nCr (キャッシュ版)
1回目 71.492s 27.765s
2回目 70.68s 28.093s
3回目 71.928s 28.131s

このプログラムのキャッシュのキーは配列データの値を文字列連結しただけなので、本気で使う場合は改良されたし。