【Java】組合せの数を求める

2016/01/31 Sun [edit]

　「階乗」「順列」とやったので、「組合せ」もやってみよう。

　「組合せ」とは簡単に言えば「n 個ものもから、r 個取り出す方法で、並べ方を問題にしない数」である。「8人の中から3人選び出してチームを作る方法は何通りあるか？」のような数を計算するのに使う。並べ方を考慮する場合は「順列」になる。

　組合せの計算は以下の式のようになるが、これも階乗計算同様、桁あふれのオーバフローを起こす可能性が高いので、一番下の「漸化式」を使おう。こちらの式を使うと多少オーバフローを防ぐことができる。また、ちょっとした計算として使うなら、オーバーフローの心配のない Ruby 版を使う手もある。開発環境がなくてもオンラインIDEで十分だろう。
　

●組合せの計算

/**<h1>n 個のものから r 個取り出した組合せの数を求める</h1>
 * <p>漸化式 : nCr = (n - r + 1) / r * nCr-1 を利用する。</p>
 * @param n ： すべての数 (1～61) (負の値はエラー)
 * @param r ： 取り出す数 (1～30) (負の値はエラー)
 * @return<b>long</b> ： 組合せの数
 */
public static final long combination(final int n, int r) {
    if (n < 0 || r < 0 || n < r) {
        throw new ArithmeticException("n = " + n + ", r = " + r);
    }

    r = Math.min(r, n - r);    //nCr = nCn-r
    if (r == 1) {
        return n;
    }

    long sum = 1;
    for (int i = 1; i <= r; i++) {
        //漸化式 : nCr = (n - r + 1) / r * nCr-1 を利用
        sum = sum * (n - i + 1) / i; //漸化式(r(i)で割り切るのに、先に nCr-1 が必要なため、 sum *= ～ としない)
    }
    return sum;
}


//メインでは...
int n = 20;
int r = 10;
long l = combination(n, r);
System.out.println(l);

　引数は２つとり、負の値では色々都合悪いので例外処理も入れた。オーバフローは n = 61 のとき r = 30 までは可能だが、心配ならループ内に負の値のチェックを入れるのも良いだろう（もちろんその分、実行速度は落ちる）。結果を double にすれば、指数形式にはなるが、上から16桁までは計算できる（17桁以降は丸められ、0 で埋まる）。

　組合せの nCr = nCn-r の性質から、r と n-r の小さい方をとったり、r = 1 のときは計算する必要ないので、条件を１つ付け加えたりしているが、少しでも計算を速くするためなので、コードを短くしたいなら取り除いても構わない（結果は変わらない）。

　ちなみに、「n 種類のものから、重複して取り出すことを許して、r 個の集まりを作る」という「重複組合せ」というものもあるが、式を比較してみると、n の値に (n + r - 1) を代入したものと同じになっていることがわかる。だから上記の関数を使って、combination(n + r - 1, r) で求められることもわかる。

　もう１つ、オーバフロー対策として任意精度整数(多倍長整数)を使って書いてみよう。実行速度はプリミティブ型と比べて約35倍ほど劣るが、桁あふれを防げるので検算には役に立つだろう。また、再帰で書く方法はただでさえ重い計算なので、避けたほうが良いだろう（約２倍の時間がかかる）[→計算時間は階乗計算の記事を参考に]。
　
●任意精度整数での組合せの計算

import java.math.BigInteger;

public static final BigInteger combination(final int n, int r) {
    if (n < 0 || r < 0 || n < r) {
        throw new ArithmeticException("n = " + n + ", r = " + r);
    }

    r = Math.min(r, n - r);    //nCr = nCn-r
    if (r == 1) {
        return new BigInteger(String.valueOf(n));
    }

    BigInteger sum = BigInteger.ONE;
    for (int i = 1; i <= r; i++) {
        //漸化式 : nCr = (n - r + 1) / r * nCr-1 を利用
        sum = sum.multiply(new BigInteger(String.valueOf((n - i + 1)))).divide(new BigInteger(String.valueOf(i)));
    }
    return sum;
}


//メインでは...
int n = 60;
int r = 30;
BigInteger b = combination(n, r);
System.out.println(b);

　ちょっと試しに練習問題をやってみよう。これはどちらかというとプログラミング問題というより数学の問題だ。

４枚のコインを投げた時、そのうち２枚が表で２枚が裏になる確率はどれくらいか？

//組み合わせでの解法
double d = (double)combination(4, 2) / Math.pow(2, 4);
System.out.println(d);	//0.375 (= 3/8)

　答えは 37.5% (= 3/8) である。「えっ？50% (1/2) じゃないの？」と思った人は気をつけよう。それはコイン４枚のうち２枚という数字で 2/4 = 1/2 のような思い込みをしているだけだ。

　簡単に解法を書いてみると、コインは表裏の２通りで４枚あるから、すべての可能性は 2 x 2 x 2 x 2 = 16 通りである。うち２枚が表（残りは必然的に裏）というのは組合せの 4C2 = 6 通りだから、確率は (起こる事象 / 全事象) で 6/16 = 3/8 = 0.375 (37.5%) となる。

　２進数がわかる人なら（プログラマーなら知ってると思うが）、表を１、裏を０としたとき、その並びは 0000 ～ 1111 つまり 0 ～ 15 (16 個) というのはすぐわかるし、そのうち２つのビットが１になっているものは、0011, 0101, 0110, 1001, 1010, 1100 の６つだから、確率は 6/16 = 3/8 となるのもわかるだろう。

　この問題なら数が少ないので、自分で数えてもすぐにわかると思うが、では「50枚のコインを投げて、25枚表、25枚裏になる確率は？」と問われたらどうだろうか？もちろん 1/2 ではない(笑)。とたんに手計算ではやってられなくなるだろう。その場合、先ほどのコードを変数に置き換えてみると、

int n = 50;
int r = 25;
double d = (double)combination(n, r) / Math.pow(2, n);
System.out.println(d);	//0.11227517265921705

のようになる（答え 11.2%）。

　「あれ？４枚のときより少なくなっているな…」と気づいた人はスルドイ。試しに 4枚～50枚でその半分の枚数が表になる確率を計算してみよう。

4枚のうち 2 枚が表の確率 = 0.375
6枚のうち 3 枚が表の確率 = 0.3125
8枚のうち 4 枚が表の確率 = 0.2734375
10枚のうち 5 枚が表の確率 = 0.24609375
12枚のうち 6 枚が表の確率 = 0.2255859375
14枚のうち 7 枚が表の確率 = 0.20947265625
16枚のうち 8 枚が表の確率 = 0.196380615234375
18枚のうち 9 枚が表の確率 = 0.1854705810546875
20枚のうち 10 枚が表の確率 = 0.17619705200195312
22枚のうち 11 枚が表の確率 = 0.16818809509277344
24枚のうち 12 枚が表の確率 = 0.1611802577972412
26枚のうち 13 枚が表の確率 = 0.15498101711273193
28枚のうち 14 枚が表の確率 = 0.14944598078727722
30枚のうち 15 枚が表の確率 = 0.14446444809436798
32枚のうち 16 枚が表の確率 = 0.13994993409141898
34枚のうち 17 枚が表の確率 = 0.13583375955931842
36枚のうち 18 枚が表の確率 = 0.13206059957155958
38枚のうち 19 枚が表の確率 = 0.1285853206354659
40枚のうち 20 枚が表の確率 = 0.12537068761957926
42枚のうち 21 枚が表の確率 = 0.12238567124768451
44枚のうち 22 枚が表の確率 = 0.11960417871932805
46枚のうち 23 枚が表の確率 = 0.11700408787760352
48枚のうち 24 枚が表の確率 = 0.11456650271348678
50枚のうち 25 枚が表の確率 = 0.11227517265921705

　つまり枚数が増えていくたびに、その半分が表になる確率はどんどん減っていく。

　余談だが、海外ではこういった「思い込みで 1/2 に見える確率」のようなイカサマ博打でカモられることもあるそうだ（日本でも江戸時代まではそういうことがあったらしい）。まぁ、賭け事なんて基本的には胴元が儲かる仕組み（だいたい胴元６：客４以上の確率にしておけば、大数の法則で胴元は常に儲かる）になっているものなんだけどね。思い込みでダマされないようにしよう(笑)。

　最後に任意精度整数[BigInteger]とプリミティブ型での組合せの計算（long を double に書き換えたものも含む）での計算結果を比較してみよう。どのコードを使うかは求める答えや実行速度などに合わせて、自由に選べば良いと思う。

●long, double, BigInteger で組合せ計算した結果の比較

70C1
long       = 70
double     = 70
BigInteger = 70
70C2
long       = 2415
double     = 2415
BigInteger = 2415
70C3
long       = 54740
double     = 54740
BigInteger = 54740
70C4
long       = 916895
double     = 916895
BigInteger = 916895
70C5
long       = 12103014
double     = 12103014
BigInteger = 12103014
70C6
long       = 131115985
double     = 131115985
BigInteger = 131115985
70C7
long       = 1198774720
double     = 1198774720
BigInteger = 1198774720
70C8
long       = 9440350920
double     = 9440350920
BigInteger = 9440350920
70C9
long       = 65033528560
double     = 65033528560
BigInteger = 65033528560
70C10
long       = 396704524216
double     = 396704524216
BigInteger = 396704524216
70C11
long       = 2163842859360
double     = 2163842859360
BigInteger = 2163842859360
70C12
long       = 10638894058520
double     = 10638894058520
BigInteger = 10638894058520
70C13
long       = 47465835030320
double     = 47465835030320
BigInteger = 47465835030320
70C14
long       = 193253756909160
double     = 193253756909160
BigInteger = 193253756909160
70C15
long       = 721480692460864
double     = 721480692460864
BigInteger = 721480692460864
70C16
long       = 2480089880334220
double     = 2480089880334220
BigInteger = 2480089880334220
70C17
long       = 7877932561061640
double     = 7877932561061640
BigInteger = 7877932561061640
70C18
long       = 23196134763125940
double     = 23196134763125940
BigInteger = 23196134763125940
70C19
long       = 63484158299081520
double     = 63484158299081528   //←上から17桁以降は丸められる(0で埋まる[指数形式])
BigInteger = 63484158299081520
70C20
long       = 161884603662657876
double     = 161884603662657888
BigInteger = 161884603662657876
70C21
long       = 385439532530137800
double     = 385439532530137790
BigInteger = 385439532530137800
70C22
long       = 19990591830327299    //←ここでオーバフロー
double     = 858478958817125120
BigInteger = 858478958817125100
70C23
long       = 41719495993726537
double     = 1791608261879217410
BigInteger = 1791608261879217600
70C24
long       = 81700679654381134
double     = 3508566179513467400
BigInteger = 3508566179513467800
70C25
long       = 150329250564061286
double     = 6455761770304780300
BigInteger = 6455761770304780752
70C26
long       = 260185241360875302
double     = 11173433833219813000
BigInteger = 11173433833219812840
70C27
long       = -259207164956705123
double     = 18208558839321176000
BigInteger = 18208558839321176480
70C28
long       = 260744142163258261
double     = 27963143931814666000
BigInteger = 27963143931814663880
70C29
long       = -258465175960438091
double     = 40498346384007450000
BigInteger = 40498346384007444240
70C30
long       = 261655728644386329
double     = 55347740058143515000
BigInteger = 55347740058143507128
70C31
long       = -257435965417228982
double     = 71416438784701310000
BigInteger = 71416438784701299520
70C32
long       = 262710669451175666
double     = 87038784768854720000
BigInteger = 87038784768854708790
70C33
long       = -256476928320147766
double     = 100226479430802400000
BigInteger = 100226479430802391940
70C34
long       = 263444050760708361
double     = 109069992321755560000
BigInteger = 109069992321755544170
70C35
long       = -256078807037830017
double     = 112186277816662850000
BigInteger = 112186277816662845432