Zenn
🐙

nCr の組合せの選び方に一意な番号を振る方法

に公開
Python
組合せ
tech

はじめに

人間、生きていたら{}_n C _ rの選び方に一意な番号を振りたくなるときもあります。

どういうことかというと、たとえば A, B, C, D から２つを選ぶ組合せは{} _ 4 C _ 2通りで、組合せのパターンは以下の６通りあるわけですが、

{}_4 C _ 2 A B C D
0 0 0 1 1
1 0 1 0 1
2 0 1 1 0
3 1 0 0 1
4 1 0 1 0
5 1 1 0 0

この左側に振った 2 という番号を与えたら、それに対応する [0, 1, 1, 0] という組合せを返してくれるような関数が欲しくなるときがありませんか？ありますよね？そう、あるんですよ。

というわけで今回作ってみました[1]。よい頭の体操になるので、皆様もぜひチャレンジしてみると面白いでしょう。

解法１：列挙して配列に保存し、インデックスで取り出す

nとrが十分に小さければ、その結果を配列に保存してインデックスで取り出すだけで事足りることも多いです。Python であれば itertools.combinations などを使って簡単に実現できます。自分で実装するとしても再帰関数を使えば簡単です。

たとえば先ほどの{} _ 4 C _ 2のケースを考えると、

  • A が 0 のときは、残りの３つから２つ選ぶ
  • A が 1 のときは、残りの３つから１つ選ぶ

となるので、{} _ 4 C _ 2は{} _ 3 C _ 2の結果と{} _ 3 C _ 1の結果を A の値でくっつけたものとみなすことができます。

一般に、{} _ n C _ rは{} _ {n-1} C _ rと{} _ {n-1} C _ {r-1}の結果を合成して得られます。再帰の基底は、n個の中から１つも選ばないケースか、n個の中からすべてを選ぶケースです。

  • r == 0: [0, 0, ..., 0]（0がn個並ぶケース）
  • n == r: [1, 1, ..., 1]（1がn個並ぶケース）

Python で実装すると以下のようになります。

def nCr(n, r):
    if r == 0:
        return [[0] * n]
    elif n == r:
        return [[1] * n]
    
    return [ [0] + cmb for cmb in nCr(n - 1, r) ] \
            + [ [1] + cmb for cmb in nCr(n - 1, r - 1) ]
output
>>> nCr(4, 2)
[[0, 0, 1, 1],
 [0, 1, 0, 1],
 [0, 1, 1, 0],
 [1, 0, 0, 1],
 [1, 0, 1, 0],
 [1, 1, 0, 0]]

>>> nCr(4, 2)[2]
[0, 1, 1, 0]

解法２：番号から対応する組合せを求める

nとrがそこそこ大きい値を取る場合（たとえば {}_{200}C_{50}）は、組合せ爆発によってパターン数が指数関数的に増大するため、すべての組合せをメモリに保持するとか、都度再帰関数で生成した組合せを前から順に辿るという計算方法は、計算量の観点から現実的ではなくなります。

というわけで少しだけ工夫する必要があるのですが、先ほど作った再帰関数について、求めたい組合せについてのみメモリに保持するよう調整すればよいです。

たとえば{} _ {10} C _ 4は{} _ 9 C _ 4と{} _ 9 C _ 3の合成ですから、k という番号（0 から数えて）に対応する組合せを求めたいときは、k < {} _ 9 C _ 4であれば１桁目が 0 になることが分かります。

このように１桁ずつ値を確定させていくようなアルゴリズムを作ればよいです。

from math import comb

def _kth_nCr(n, r, k):
    """アルゴリズム本体"""
    if r == 0:
        return [0] * n
    elif n == r:
        return [1] * n
    
    c = comb(n - 1, r)
    if k < c:
        return [0] + _kth_nCr(n - 1, r, k)
    return [1] + _kth_nCr(n - 1, r - 1, k - c)

def kth_nCr(n, r, k):
    """バリデーション付きのラッパー"""
    c = comb(n, r)
    if k >= c:
        raise ValueError(f"k must be smaller than comb({n}, {r}) == {c}, but actual value {k}")
    
    return _kth_nCr(n, r, k)
output
>>> kth_nCr(4, 2, 2)
[0, 1, 1, 0]

>>> [ kth_nCr(4, 2, k) for k in range(6) ]
[[0, 0, 1, 1],
 [0, 1, 0, 1],
 [0, 1, 1, 0],
 [1, 0, 0, 1],
 [1, 0, 1, 0],
 [1, 1, 0, 0]]

オマケ：組合せに対応する番号を求める

『解法２』で作ったアルゴリズムと逆のことをすれば、組合せに対応する番号を一意に求めることも可能です。

from math import comb

def _index_nCr(n, r, xs):
    """アルゴリズム本体"""
    if r == 0:
        return 0
    elif n == r:
        return 0
    
    if xs[0] == 0:
        return _index_nCr(n - 1, r, xs[1:])
    return comb(n - 1, r) + _index_nCr(n - 1, r - 1, xs[1:])

def index_nCr(n, r, xs):
    """バリデーション付きのラッパー"""
    if any( x not in {0, 1} for x in xs ):
        raise ValueError(f"invalid value detected in xs")
    elif len([ x for x in xs if x == 1 ]) != r:
        raise ValueError(f"number of 1 in xs must be equal to r")
    
    return _index_nCr(n, r, xs)
output
>>> [ index_nCr(4, 2, cmb) for cmb in nCr(4, 2) ]
[0, 1, 2, 3, 4, 5]

>>> [ index_nCr(5, 3, cmb) for cmb in nCr(5, 3) ]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> [ index_nCr(6, 2, cmb) for cmb in nCr(6, 2) ]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

これでインデックスと組合せの間に全単射を定義することができました。

追加問題

順列に対しても同じことができるはずですので、興味のある人はやってみるとよいでしょう。

おしまい

欲求が満たされたので今回はこれでおしまいです。ありがとうございました。

脚注

  1. 探せばどこかに転がっているだろうと思うのですが、「組合せ」とか「番号」みたいなワードが一般的過ぎて、どう検索したら辿り着けるのか見当がつきません。ご存じでしたらぜひ教えてください。 ↩︎

Discussion