【Java】組み合わせを実装してみた。

数学の組み合わせを Java で実装してみた

異なるn個の中から異なるr個とる組み合わせを Java で実装してみました。
r個の数だけループする実装は見たことがありますが、
r個が変わっても大丈夫なようにしたくていろいろ考えました。

ソースコード

下記コードは 5個 の中から 3個 とるようになっています。

import java.util.ArrayList;
import java.util.List;

public class Trial {

    public static void main(String[] args) {
        Trial me = new Trial();
        me.exec(args);
    }

    public void exec(String[] args) {
        // 文字列の配列
        String[] strArray = new String[] { "a", "b", "c", "d", "e" };
        // 組み合わせを取得
        String[][] combinations = getCombinations(strArray, 3);
        // 結果出力
        for (String[] combination : combinations) {
            for (String str : combination) {
                System.out.print("  " + str);
            }
            System.out.println();
        }
    }

    private String[][] getCombinations(String[] strArray, int selectCount) {
        // 結果を詰める用のリスト
        List<String[]> list = new ArrayList<>();
        // ちょいちょい使うので変数に保持
        int len = strArray.length;
        // 配列の長さから２進数での最大値を求める。
        int dec = 0;
        for (int i = 0; i < len; i++) {
            dec += Math.pow(2, i);
        }
        // 最大値からデクリメントしていく。
        for (int num = dec; 0 < num; num--) {
            // ２進数表記の文字列にする。（０埋めはされない）
            String bin = Integer.toBinaryString(num);
            if (!isCombination(bin, selectCount)) {
                // 1 の数が選択数と一致しない場合は無視する。
                continue;
            }
            int j = bin.length() - 1;
            int tmplen = len - bin.length();
            String[] combination = new String[selectCount];
            int idx = selectCount - 1;
            for (int i = len - 1; tmplen <= i; i--) {
                if (bin.charAt(j--) == '1') {
                    combination[idx--] = strArray[i];
                }
            }
            list.add(combination);
        }
        return list.toArray(new String[0][0]);
    }

    private boolean isCombination(String str, int selectCount) {
        int sum = 0;
        for (int i = 0; i < str.length(); i++) {
            sum += Character.getNumericValue(str.charAt(i));
        }
        if (sum == selectCount) {
            return true;
        }
        return false;
    }
}

実行結果

  a  b  c
  a  b  d
  a  b  e
  a  c  d
  a  c  e
  a  d  e
  b  c  d
  b  c  e
  b  d  e
  c  d  e

5個から3個をとる組み合わせは、5! / (2! * (5 - 2)!) = 10
たぶん合ってる。

最後に

パフォーマンスや大きな数字を扱うことを考えると改善の余地は大いにあると思います。

以上