清一色の手牌は何通りあるか（13重ループ、再帰、itertools、包除原理）

※上の牌姿はWikipediaの記事より抜粋

　麻雀において、清一色の形、つまり同じ色の牌だけを使った手牌（13枚の組み合わせ）は何通りあるかという問題を考える。もし、全く同じ牌が4つだけでなく無限に存在するのであれば、これはいわゆる重複組合せの問題になり、以下の式で簡単に計算できる。

_9H _{13} = _{21}C_{13}=203490

　しかし現実には同じ牌は4種類しか存在しないので、重複数の上限が存在する。9999999999999という手牌は存在しない。

　この数をプログラムを用いて色々な方法で求めてみる。

13重ループ

簡潔さ：×
保守性：×
可読性：×（ある意味◎）

　今だったら絶対にこんなプログラムは書かないが、その昔13重ループを用いてこの数値を求めたことがある。美しさのかけらもないコードだが、何をやってるかを示す、という意味では一番わかりやすいかもしれない。

def equal4(a,b,c,d):
    if a==b and b==c and c==d:
        return True
    return False

ans = 0

for a in range(1,10):
    for b in range(a,10):
        for c in range(b,10):
            for d in range(c,10):
                for e in range(d,10):
                    if equal4(a,b,c,d):
                        e += 1
                    for f in range(e,10):
                        if equal4(b,c,d,e):
                            f += 1
                        for g in range(f,10):
                            if equal4(c,d,e,f):
                                g += 1
                            for h in range(g,10):
                                if equal4(d,e,f,g):
                                    h += 1
                                for i in range(h,10):
                                    if equal4(e,f,g,h):
                                        i += 1
                                    for j in range(i,10):
                                        if equal4(f,g,h,i):
                                            j += 1
                                        for k in range(j,10):
                                            if equal4(g,h,i,j):
                                                k += 1
                                            for l in range(k,10):
                                                if equal4(h,i,j,k):
                                                    l += 1
                                                for m in range(l,10):
                                                    if equal4(i,j,k,l):
                                                        m += 1
                                                    if m == 10:
                                                        continue
                                                    ans += 1

print(ans)

93600

　このようなコードは、冗長なだけでなく、ある日麻雀のルールが変わって同じ牌の上限が5枚になった時に関係するすべての箇所の修正が必要となる。趣味でも仕事でも、なるべく書かない方が良いだろう。

　再帰

簡潔さ：○
保守性：◎
可読性：△

　上のコードを見ていると、同じような記述を繰り返していることに気づく。配列を用いればよりスマートに書けそうだが、再帰処理を使って更に短縮して書くこともできる。

def dfs(v):
    if len(v) == 13:
        return 1
    last_num = 1
    if len(v) > 0:
        last_num = v[-1]
    if v.count(last_num) == 4:
        last_num += 1
    ans = 0
    for i in range(last_num,10):
        ans += dfs(v+[i])
    return ans

print(dfs([]))

93600

　自分自身の末尾に1から9までの数字をくっつけた「子供」を作る、という処理を「子供」自身も繰り返すようにすると、ねずみ算式（ねずみ算式とはなんのだろう？　筆者は「ねずみ算」なる計算問題を解いたことも見たこともない）に色々な手牌候補の数字が生まれてくる。このままだと無限ループしてしまうので、長さが13になったところで打ち切る。また、子供が既に同じ種類が4人いるのであれば、その子供は生み出さないようにすることで、4枚の上限を保っている。

　これならば、ある日突然麻雀のルールが変わっても、対応した1つの数値を変えるだけで保守できる。また、ある程度ロジックを制御できるので、例えば「数牌の1と2は共存してはならない」といった局所的なルールが追加されても対応できる。

　しかし、可読性はあまりあるとは言えないだろう。書いた作者にとっては自明に感じられるが、これを事前知識なしで見て一瞬で挙動を把握するのは難しい。他人と共有するにはやや不親切と言える。

itertools

簡潔さ：○
保守性：○
可読性：◎

　Pythonには便利なライブラリが多い。itertoolsもそのようなものの一つである。これを使うと、重複組合せのすべての場合を列挙してくれる。それらについて、条件を満たすものだけを数える。

import itertools

ans = 0

for case in itertools.combinations_with_replacement(range(1, 10), 13):
    isFail = False
    for n in range(1, 10):
        if case.count(n) > 4:
            isFail = True
    if isFail:
        continue
    ans += 1

print(ans)

93600

　ややライブラリ任せというか力任せな手法だが、少ない記述量と「何をやっているか」を示す、という点を両立できている。ライブラリのコマンドは（多くの人が共有できるであろうという）名前の付け方をされているので、おおよその場合フルスクラッチで書くよりも第三者が理解しやすいコードになる。

　少し無駄な計算が多くなるのと、局所的なルール変更に対して保守性がないのが欠点と言えば欠点だが、そこまで大きなデメリットとは言えない。

包除原理

　本番。というかこれを知ったのでこの記事を書きたくなったというのが実情だ。

　重複数に上限数のある重複組合せについては、昔は一般化が難しいのではと思っていたが、実は包除原理によって計算できる。

「重複数4枚以下の重複組合せ」は、「全ての重複組合せ」から「重複数5枚以上の重複組合せ」を除いたものに等しい。

　では「重複数5枚以上の重複組合せ」はどうやって求めるか。これは、11111....みたいなパターンと..22222...みたいなパターンを全て列挙していけばいい。先に5つのグループを確保すれば、残りの8枚をどう埋めるかは普通の重複組合せと全く同じ話になる。どれを確保するかは1～9の9通り。よって、

9 \cdot _{9}H _{8}

　で計算できる。

　しかし実はこれだけではダブりがあって、1111122222...みたいなパターンは1のグループでも2のグループでも数えてしまっている。なのでそれだけは除く必要がある。この場合、グループの確保は$9C2$通り。残りの枚数は3枚になる。よって、

_9 C _2 \cdot _9 H _ 3

　だったら更に111112222233333...のダブリは...とはならない。枚数の上限が13枚なので。（逆に、麻雀のルールが変更されて手牌の枚数が16枚とかになったらそれも考慮する必要がある）

　今まで言った議論をまとめると、求める数は以下の計算式になる。

_9H _{13} - 9 \cdot _{9}H _{8} + _9 C _2 \cdot _9 H _ 3 \\
=203490 - 115830 + 5940 \\
=93600

　一応プログラムでも書くと以下の通り。

from scipy.special import comb


def h(n, r):
    return comb(n+r-1, r)


ans = h(9, 13) - comb(9, 1)*h(9, 8) + comb(9, 2)*h(9, 3)
print(ans)

93600

　今まであげてきた方法と比べて、「手牌の状態を保持する」という機能がないため、コードの性質の比較は行わない。