【Java】順列の数を求める

2016/01/30 Sat [edit]

　せっかく階乗の計算をやったので順列の数を求める計算をやってみよう。確率などの計算にも不可欠なので、ライブラリ化しておくと良いかもしれない。

　「順列」とは簡単に言えば「n 個ものもから、r 個取り出した並べ方」である。「8人の中から3人選び出して一列に並べる方法は何通りあるか？」のような数を計算するのに使う。並べ方を考えない場合は「組合せ」になる。順列は以下の式から、ほとんど階乗の計算と変わらないことがわかる。階乗の計算では「1～n」を掛けあわせたものだったが、順列の計算は「(n-r+1)～n」の掛けあわせになるだけだ。

　階乗計算同様、桁あふれのオーバフローを起こす可能性が高いので、ちょっとした計算として使うなら、オーバーフローの心配のない Ruby 版を使う手もある。開発環境がなくてもオンラインIDEで十分だろう。

●while ループでの順列計算

/**<h1>n 個のものから r 個取り出した並び方(順列)の数を求める</h1>
 * <p>nPr の計算。</p>
 * @param n ： すべての数 (1～20) (負の値はエラー)
 * @param r ： 取り出す数 (1～20) (負の値、r > n はエラー)
 * @return<b>long</b> ： 並び方(順列)の数
 */
public static final long permutation(int n, final int r) {
    if (n < 0 || r < 0 || n < r) {
        throw new ArithmeticException("n = " + n + ", r = " + r);
    }

    final int t = n - r;
    long sum = 1;
    while (n > t) {
        sum *= n--;
    }
    return sum;
}


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

　コードの内容は階乗の計算と変わらないので、説明はいらないだろう。今回は引数を２つとるので、負の値では色々都合悪いので例外処理も入れた。階乗のプリミティブ型のオーバフローは 21! だったので、気をつけた方がいいが、心配ならループ内に負の値のチェックを入れるのも良いだろう（もちろんその分、実行速度は落ちるが）。結果を double にすれば、指数形式にはなるが、上から16桁までは計算できる（17桁以降は丸められ、0 で埋まる）。

　もう１つ前回と同じように for ループを使った書き方もしてみよう。while の方が若干実行速度が速いが（といっても決定的な差はないのでどちらでも良い）、複数の書き方を考えておくと、色々改造しやすい。

●for ループでの順列計算

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

    long sum = 1;
    for (int i = n - r + 1; i <= n; i++) {
        sum *= i;
    }
    return sum;
}

//※メインは先の例と同じで良い

　最後にもう１つ、オーバフロー対策として任意精度整数(多倍長整数)を使って書いてみよう。実行速度はプリミティブ型と比べて約35倍ほど劣るが、桁あふれを防げるので検算には役に立つだろう。階乗計算のときと同じ理由で、while で逆順で計算すると遅くなるので、for ループの方を使った。r = 1 のときは計算する必要ないので、条件を１つ付け加えたが（少しでも速くするため）、コードを短くしたいなら取り除いても構わない（結果は変わらない）。また、再帰で書く方法はただでさえ重い計算なので、避けたほうが良いだろう（約２倍の時間がかかる）[→計算時間は階乗計算の記事を参考に]。
　
●任意精度整数での順列計算

import java.math.BigInteger;

public static final BigInteger permutation(final int n, final int r) {
    if (n < 0 || r < 0 || n < r) {
        throw new ArithmeticException("n = " + n + ", r = " + r);
    }
    if (r == 1) {
        return new BigInteger(String.valueOf(n));
    }

    BigInteger sum = BigInteger.ONE;
    for (int i = n - r + 1; i <= n; i++) {
        sum = sum.multiply(new BigInteger(String.valueOf(i)));
    }
    return sum;
}


//メインでは...
int n = 20;
int r = 10;
BigInteger b = permutation(n, r);
System.out.println(b);

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

●long, double, BigInteger で順列計算した結果の比較

50P0
long       = 1
double     = 1
BigInteger = 1
50P1
long       = 50
double     = 50
BigInteger = 50
50P2
long       = 2450
double     = 2450
BigInteger = 2450
50P3
long       = 117600
double     = 117600
BigInteger = 117600
50P4
long       = 5527200
double     = 5527200
BigInteger = 5527200
50P5
long       = 254251200
double     = 254251200
BigInteger = 254251200
50P6
long       = 11441304000
double     = 11441304000
BigInteger = 11441304000
50P7
long       = 503417376000
double     = 503417376000
BigInteger = 503417376000
50P8
long       = 21646947168000
double     = 21646947168000
BigInteger = 21646947168000
50P9
long       = 909171781056000
double     = 909171781056000
BigInteger = 909171781056000
50P10
long       = 37276043023296000
double     = 37276043023296000
BigInteger = 37276043023296000
50P11
long       = 1491041720931840000
double     = 1491041720931840000
BigInteger = 1491041720931840000
50P12
long       = 2810394895213105152    //←ここでオーバフロー
double     = 58150627116341756000   //←上から17桁以降は丸められる(0で埋まる[指数形式])
BigInteger = 58150627116341760000
50P13
long       = -3885458424159313920
double     = 2209723830420986700000
BigInteger = 2209723830420986880000
50P14
long       = 3811990895781797888
double     = 81759781725576510000000
BigInteger = 81759781725576514560000
50P15
long       = 8104463732177862656
double     = 2943352142120754600000000
BigInteger = 2943352142120754524160000
50P16
long       = 6955069520581918720
double     = 103017324974226400000000000
BigInteger = 103017324974226408345600000
50P17
long       = -3335309258438934528
double     = 3502589049123698000000000000
BigInteger = 3502589049123697883750400000
50P18
long       = 615258913772470272
double     = 115585438621082040000000000000
BigInteger = 115585438621082030163763200000
50P19
long       = 1241541167009497088
double     = 3698734035874625300000000000000
BigInteger = 3698734035874624965240422400000
50P20
long       = 1594288029875306496
double     = 114660755112113380000000000000000
BigInteger = 114660755112113373922453094400000
50P21
long       = -7511591324869459968
double     = 3439822653363401000000000000000000
BigInteger = 3439822653363401217673592832000000
50P22
long       = 3524780463300280320
double     = 99754856947538630000000000000000000
BigInteger = 99754856947538635312534192128000000
50P23
long       = 6460132603860090880
double     = 2793135994531082000000000000000000000
BigInteger = 2793135994531081788750957379584000000
50P24
long       = 8402883640836489216
double     = 75414671852339210000000000000000000000
BigInteger = 75414671852339208296275849248768000000
50P25
long       = -2885954222765899776
double     = 1960781468160819400000000000000000000000
BigInteger = 1960781468160819415703172080467968000000
50P26
long       = 1638120725690712064
double     = 49019536704020485000000000000000000000000
BigInteger = 49019536704020485392579302011699200000000
50P27
long       = 2421409269157986304
double     = 1176468880896491700000000000000000000000000
BigInteger = 1176468880896491649421903248280780800000000
50P28
long       = 352180969505030144
double     = 27058784260619310000000000000000000000000000
BigInteger = 27058784260619307936703774710457958400000000
50P29
long       = 7747981329110663168
double     = 595293253733624800000000000000000000000000000
BigInteger = 595293253733624774607483043630075084800000000
50P30
long       = -3313088752062038016
double     = 12501158328406122000000000000000000000000000000
BigInteger = 12501158328406120266757143916231576780800000000
50P31
long       = 7525201253597446144
double     = 250023166568122460000000000000000000000000000000
BigInteger = 250023166568122405335142878324631535616000000000
50P32
long       = -4595128771324936192
double     = 4750440164794326500000000000000000000000000000000
BigInteger = 4750440164794325701367714688167999176704000000000
50P33
long       = -8925341589010644992
double     = 85507922966297880000000000000000000000000000000000
BigInteger = 85507922966297862624618864387023985180672000000000
50P34
long       = -4156854423504551936
double     = 1453634690427063900000000000000000000000000000000000
BigInteger = 1453634690427063664618520694579407748071424000000000
50P35
long       = 7277305518765375488
double     = 23258155046833023000000000000000000000000000000000000
BigInteger = 23258155046833018633896331113270523969142784000000000
50P36
long       = -1520881660776677376
double     = 348872325702495330000000000000000000000000000000000000
BigInteger = 348872325702495279508444966699057859537141760000000000
50P37
long       = -2845599177163931648
double     = 4884212559834935000000000000000000000000000000000000000
BigInteger = 4884212559834933913118229533786810033519984640000000000
50P38
long       = -99301155712008192
double     = 63494763277854150000000000000000000000000000000000000000
BigInteger = 63494763277854140870536983939228530435759800320000000000
50P39
long       = -1191613868544098304
double     = 761937159334249800000000000000000000000000000000000000000
BigInteger = 761937159334249690446443807270742365229117603840000000000
50P40
long       = 5338991519724470272
double     = 8381308752676747000000000000000000000000000000000000000000
BigInteger = 8381308752676746594910881879978166017520293642240000000000
50P41
long       = -1950317023883952128
double     = 83813087526767480000000000000000000000000000000000000000000
BigInteger = 83813087526767465949108818799781660175202936422400000000000
50P42
long       = 893890858753982464
double     = 754317787740907300000000000000000000000000000000000000000000
BigInteger = 754317787740907193541979369198034941576826427801600000000000
50P43
long       = 7151126870031859712
double     = 6034542301927258500000000000000000000000000000000000000000000
BigInteger = 6034542301927257548335834953584279532614611422412800000000000
50P44
long       = -5282344130905636864
double     = 42241796113490810000000000000000000000000000000000000000000000
BigInteger = 42241796113490802838350844675089956728302279956889600000000000
50P45
long       = 5199423361985282048
double     = 253450776680944840000000000000000000000000000000000000000000000
BigInteger = 253450776680944817030105068050539740369813679741337600000000000
50P46
long       = 7550372736216858624
double     = 1267253883404724100000000000000000000000000000000000000000000000
BigInteger = 1267253883404724085150525340252698701849068398706688000000000000
50P47
long       = -6691997202551668736
double     = 5069015533618896400000000000000000000000000000000000000000000000
BigInteger = 5069015533618896340602101361010794807396273594826752000000000000
50P48
long       = -1629247533945454592
double     = 15207046600856688000000000000000000000000000000000000000000000000
BigInteger = 15207046600856689021806304083032384422188820784480256000000000000
50P49
long       = -3258495067890909184
double     = 30414093201713376000000000000000000000000000000000000000000000000
BigInteger = 30414093201713378043612608166064768844377641568960512000000000000
50P50
long       = -3258495067890909184
double     = 30414093201713376000000000000000000000000000000000000000000000000
BigInteger = 30414093201713378043612608166064768844377641568960512000000000000