Javaで数学の組み合わせ(Combination)を実装する

13572 ワード
アルゴリズム プログラミング教育 組み合わせ Java 順列組み合わせ Java テキストリンク

最近、諸事情によりJavaで数学の組み合わせを実装する機会がありました。その際レビューしたコードが非効率だったので、Qiitaの記事にしてみました。

高校の授業で順列と組み合わせを習ったと思いますが、簡単におさらいすると、例えば「6個の集合から2個を選択する組み合わせ」の数は以下のようになります。

【公式】　_n \mathrm{ C }_k = \frac{n!}{k!(n-k)!} 　（0 < k <= n であること）

_6 \mathrm{ C }_2 =  \frac{6!}{2!(6-2)!} =  \frac{6!}{2!\times4!} = \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{2 \times 1 \times 4 \times 3 \times 2 \times 1} = \frac{6 \times 5 }{2 \times 1} = 15

また、組み合わせの結果としては{A, B}と{B, A}は同じものを意味します。

「コードが非効率だった」とは結果の数（例では15）よりも多い回数の処理を行っていたためです。
「必要最低限の処理回数で、正しい組み合わせを列挙できる」ことを「効率がよい」ということにします。
これは、組み合わせの対象となる集合（コレクション）の数が非常に大きい場合を想像すれば分かるかと思います。

N個集合から2個を選択する場合と3個を選択する場合を例として実装してみました。
最も効率的に組み合わせを求める考え方のイメージは以下の通りです。
なお、集合内に重複する値は存在しない前提とします。

Combination.java
package com.example.demo;

public class Combination {

    public static void main(String[] args) {
        String[] list = { "A", "B", "C", "D", "E", "F"};
        nCombination2(list);
        nCombination3(list);

        String[] list2 = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
        nCombination2(list2);
        nCombination3(list2);
    }

    private static void nCombination2(String[] list) {
        int count = list.length;
        int num = 0;
        for (int i = 0; i < count - 1; i++) {
            for (int j = i + 1; j < count; j++) {
                num++;
                System.out.print(num + " {" + list[i] + ", " + list[j] + "}\t");
            }
            System.out.println();
        }
        System.out.println("[answer] " + count + "C2 : " + num);
    }

    private static void nCombination3(String[] list) {
        int count = list.length;
        int num = 0;
        for (int i = 0; i < count - 2; i++) {
            for (int j = i + 1; j < count - 1; j++) {
                for (int k = j + 1; k < count; k++) {
                    num++;
                    System.out.print(num + " {" + list[i] + ", " + list[j] + ", " + list[k] + "}\t");
                }
            }
            System.out.println();
        }
        System.out.println("[answer] " + count + "C3 : " + num);
    }
}

ポイントは繰り返しループの入れ子と開始値と終了値です。

  • １つ目の繰り返しループ　：　１つ目の要素の選択
  • ２つ目の繰り返しループ　：　２つ目の要素の選択
  • ３つ目の繰り返しループ　：　３つ目の要素の選択　（nC3の場合）

組み合わせでは{A, B}を列挙した後に{B, A}を選ぶ必要がないため、入れ子の繰り返しループの開始値は外の入れ子ループの開始値より前を選択しないようにします。

実行結果
1 {A, B}    2 {A, C}    3 {A, D}    4 {A, E}    5 {A, F}    
6 {B, C}    7 {B, D}    8 {B, E}    9 {B, F}    
10 {C, D}   11 {C, E}   12 {C, F}   
13 {D, E}   14 {D, F}   
15 {E, F}   
[answer] 6C2 : 15
1 {A, B, C} 2 {A, B, D} 3 {A, B, E} 4 {A, B, F} 5 {A, C, D} 6 {A, C, E} 7 {A, C, F} 8 {A, D, E} 9 {A, D, F} 10 {A, E, F}    
11 {B, C, D}    12 {B, C, E}    13 {B, C, F}    14 {B, D, E}    15 {B, D, F}    16 {B, E, F}    
17 {C, D, E}    18 {C, D, F}    19 {C, E, F}    
20 {D, E, F}    
[answer] 6C3 : 20
1 {A, B}    2 {A, C}    3 {A, D}    4 {A, E}    5 {A, F}    6 {A, G}    7 {A, H}    8 {A, I}    9 {A, J}    
10 {B, C}   11 {B, D}   12 {B, E}   13 {B, F}   14 {B, G}   15 {B, H}   16 {B, I}   17 {B, J}   
18 {C, D}   19 {C, E}   20 {C, F}   21 {C, G}   22 {C, H}   23 {C, I}   24 {C, J}   
25 {D, E}   26 {D, F}   27 {D, G}   28 {D, H}   29 {D, I}   30 {D, J}   
31 {E, F}   32 {E, G}   33 {E, H}   34 {E, I}   35 {E, J}   
36 {F, G}   37 {F, H}   38 {F, I}   39 {F, J}   
40 {G, H}   41 {G, I}   42 {G, J}   
43 {H, I}   44 {H, J}   
45 {I, J}   
[answer] 10C2 : 45
1 {A, B, C} 2 {A, B, D} 3 {A, B, E} 4 {A, B, F} 5 {A, B, G} 6 {A, B, H} 7 {A, B, I} 8 {A, B, J} 9 {A, C, D} 10 {A, C, E}    11 {A, C, F}    12 {A, C, G}    13 {A, C, H}    14 {A, C, I}    15 {A, C, J}    16 {A, D, E}    17 {A, D, F}    18 {A, D, G}    19 {A, D, H}    20 {A, D, I}    21 {A, D, J}    22 {A, E, F}    23 {A, E, G}    24 {A, E, H}    25 {A, E, I}    26 {A, E, J}    27 {A, F, G}    28 {A, F, H}    29 {A, F, I}    30 {A, F, J}    31 {A, G, H}    32 {A, G, I}    33 {A, G, J}    34 {A, H, I}    35 {A, H, J}    36 {A, I, J}    
37 {B, C, D}    38 {B, C, E}    39 {B, C, F}    40 {B, C, G}    41 {B, C, H}    42 {B, C, I}    43 {B, C, J}    44 {B, D, E}    45 {B, D, F}    46 {B, D, G}    47 {B, D, H}    48 {B, D, I}    49 {B, D, J}    50 {B, E, F}    51 {B, E, G}    52 {B, E, H}    53 {B, E, I}    54 {B, E, J}    55 {B, F, G}    56 {B, F, H}    57 {B, F, I}    58 {B, F, J}    59 {B, G, H}    60 {B, G, I}    61 {B, G, J}    62 {B, H, I}    63 {B, H, J}    64 {B, I, J}    
65 {C, D, E}    66 {C, D, F}    67 {C, D, G}    68 {C, D, H}    69 {C, D, I}    70 {C, D, J}    71 {C, E, F}    72 {C, E, G}    73 {C, E, H}    74 {C, E, I}    75 {C, E, J}    76 {C, F, G}    77 {C, F, H}    78 {C, F, I}    79 {C, F, J}    80 {C, G, H}    81 {C, G, I}    82 {C, G, J}    83 {C, H, I}    84 {C, H, J}    85 {C, I, J}    
86 {D, E, F}    87 {D, E, G}    88 {D, E, H}    89 {D, E, I}    90 {D, E, J}    91 {D, F, G}    92 {D, F, H}    93 {D, F, I}    94 {D, F, J}    95 {D, G, H}    96 {D, G, I}    97 {D, G, J}    98 {D, H, I}    99 {D, H, J}    100 {D, I, J}   
101 {E, F, G}   102 {E, F, H}   103 {E, F, I}   104 {E, F, J}   105 {E, G, H}   106 {E, G, I}   107 {E, G, J}   108 {E, H, I}   109 {E, H, J}   110 {E, I, J}   
111 {F, G, H}   112 {F, G, I}   113 {F, G, J}   114 {F, H, I}   115 {F, H, J}   116 {F, I, J}   
117 {G, H, I}   118 {G, H, J}   119 {G, I, J}   
120 {H, I, J}   
[answer] 10C3 : 120

numの値と組み合わせの数が等しいため、必要最低限の処理回数で組み合わせを求められたことが分かるかと思います。

nCombination2とnCombination3の作りを見比べると、繰り返しループの数が変わっているだけです。次にnCombination4を追加しようとしたら、どのような実装になるのか想像がつくのではないでしょうか。