[Javaの小枝] combination (組合せ)を列挙する

組合せの列挙

こういう需要があるということは順列でなくて組合せの需要もあるに違いないということで記事化する。弊社内でこの小さなコードは金融商品をいくつか組合せてポートフォリオというものを作り、その中から性質の良いものを選びだす、といった用途の製品に使われている。動作原理は前記事とほとんどかわらない。

Combination.java

    private enum Operation {add, remove};
    private static<T> Set<T> apply(Set<T> src, Operation operation, T item) {
        Set<T> result = new HashSet<T>(src);
        if (Operation.add == operation) result.add(item);
        if (Operation.remove == operation) result.remove(item);
        return result;
    }

    private static<T> Set<Set<T>> _combination(Set<T> selected, int depth, Set<T> pool) {
        if (depth == 0) return apply(new HashSet<>(), Operation.add, selected); // 選択済みのもののみ要素に持つ集合をかえす
        Set<Set<T>> result = new HashSet<Set<T>>();
        for (T item : pool) {
            result.addAll(
                    _combination(
                            apply(selected, Operation.add, item), // item を選択済みに変更
                            depth - 1, 
                            apply(pool, Operation.remove, item)  // pool の中からは取り除く
                    )
            );
        }
        return result;
    }
    public static<T> Set<Set<T>> combination(Set<T> src, int k) {return _combination(new HashSet<T>(), k, src);}

使い方

こんな感じ。

Main.java

    public static void main(String[] args) {

        Set<Integer> src = new HashSet<Integer>() {{
                add(0); add(1); add(2); add(3); add(4); add(5);
        }};

        System.out.println(combination(src, 2)); // 上記集合のなかから2つを取りだした集合を全て列挙する

    }