組み合わせ問題をJavaで | ジョイタスネット

問題
袋に9つのボールが入っていてそのひとつひとつに１〜９の番号がついている。ちょうどビリヤードの球が袋に9つ入っている様子を想像してもらえればよい。
その袋から３つ取り出してその番号の合計が１０になる組み合わせを列挙せよ。

プログラム問題を解いていて中級くらいになってくると登場する順列や組み合わせ。
上のような問題がでて「詰んで」しまう人も多いのではないだろうか？
それはそうだこの手の問題を一から考えていたら日が暮れてしまう。
この手の問題は「解き方を知ってるか知ってないか」が全てなのだ。（プログラミングの問題にはそういった物が多く存在する)

まずは一番簡単と思われる組み合わせ(Combination)からやっていこう。
今回の場合だと9個の中から3個を取り出す組み合わせなので9C3で84通り。
この9C3のCはCombinationのCだ。9×8×7を3×2×1で割るという計算方法をなんとなく覚えている人もいるだろう。

すべて列挙すると以下となる。

124 125 126 127 128 129 134 135 136 137 138 139 145 146 147 148 149 156 157 158 159 167 168 169 178 179 189 
235 236 237 238 239 245 246 247 248 249 256 257 258 259 267 268 269 278 279 289 
346 347 348 349 356 357 358 359 367 368 369 378 379 389 
457 458 459 467 468 469 478 479 489 
568 569 578 579 589 
679 689 


この問題をJavaで解いてみよう。
３桁の数字をつくるので３重forを作成する。
最初のループでは1つ目（百の位)なので1~7まで回せばよさそうだ。この際、８、９まで回さなくてよいことに注意する。(789が最大)
2桁目のループでは1桁目でとりだした値+1から8まで回せば良い。
3桁目のループでは２桁目でとりだした値+1から9まで回せば良い。

[解答例]

01public static void main(String[] args) {
02       
03    for(int i=1;i<=7;i++){
04      System.out.println();
05      for(int j=i+1;j<=8;j++){
06        for(int k=j+1;k<=9;k++){
07          System.out.print(""+i+j+k+" ");       
08        }
09      }
10    }
11     
12  }

これで上記の組み合わせがすべて得られる。見やすくするため最初のforのあとで改行処理をいれた。

今回の問題ではこの中から桁の合計が10になるものをピックアップすればよいので以下のように変更する。

01public static void main(String[] args) {    
02    for(int i=1;i<=7;i++){
03      for(int j=i+1;j<=8;j++){
04        for(int k=j+1;k<=9;k++){
05          if(i+j+k==10){
06            System.out.printf("[%d,%d,%d]%n",i,j,k);  
07          }       
08        }
09      }
10    }
11  }

[結果]

1[1,2,7]
2[1,3,6]
3[1,4,5]
4[2,3,5]

答えが得られた。

最後に汎用性を持たせるためにマジックナンバーを定数化しよう。

01public static void main(String[] args) {  
02    final int MIN=1,MAX=9,TOTAL=10;
03    for(int i=MIN;i<=MAX-2;i++){
04      for(int j=i+1;j<=MAX-1;j++){
05        for(int k=j+1;k<=MAX;k++){
06          if(i+j+k==TOTAL){
07            System.out.printf("[%d,%d,%d]%n",i,j,k);  
08          }       
09        }
10      }
11    }
12  }

以上で終了だ。「やはり知ってるか知ってないか」と言わざるをえない。
プログラミングによる組み合わせ,組み合わせ問題の第一歩としてまずは今回の多重forによる組み合わせを理解しよう。

[確認問題]
以下のお菓子の中から2つを選択する。ただし、合計金額は200円以内でなければならない。
アメ:30円
チョコ:120円
ガム:100円
ポテチ:80円
ビスケット:90円
条件を満たす組み合わせをすべて列挙せよ。
出力フォーマットは以下のようにすること
[アメ(30),チョコ(120)]
[アメ(30),ガム(100)]
.
.
.

[解答例]

01public class Main {
02  public static void main(String[] args) {
03    Snack[] snacks={
04        new Snack("アメ",30),
05        new Snack("チョコ",120),
06        new Snack("ガム",100),
07        new Snack("ポテチ",80),
08        new Snack("ビスケット",90),
09    };
10     
11    for(int i=0;i<snacks.length-1;i++){
12      for(int j=i+1;j<snacks.length;j++){
13        if(snacks[i].price+snacks[j].price <=200){
14          System.out.printf("[%s(%d),%s(%d)]%n",snacks[i].name,snacks[i].price,snacks[j].name,snacks[j].price);
15        }
16      }
17    } 
18  } 
19}
20class Snack{
21  String name;
22  int price;
23  Snack(String name,int price){
24    this.name=name;
25    this.price=price;
26  }
27}

[組み合わせ問題をJavaで（重複組合せ)はこちら]