Javaで組み合わせを生成する - アルゴリズム学習(その2)

Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1) - $shibayu36->blog;で順列を作ったので、続いて組み合わせを作ってみた。

考え方

いろんな考え方があると思うけど、僕が最初に思いついたのは次の考え方。

[ 1, 2, 3, 4, 5 ]から3つ取り出す組み合わせを考える
まず、1を取り出して、[ 2, 3, 4, 5 ]から2つ取り出す組み合わせのリストを作り、全てのリストの先頭に1を結合する
次に、2を取り出して、[ 3, 4, 5 ]から2つ取り出す組み合わせのリストを作り、全てのリストの先頭に2を結合する
- 組み合わせなので、前に取り出した1を使ったらだめなことに注意
次に3を取り出して、[ 4, 5 ]から2つ取り出す組み合わせのリストを作り(つまり [4, 5]だけど)、全てのリストの先頭に3を結合する
1, 2, 3を取り出して作り出したリストを全て結合する

これで再帰的な構造になっているので、再帰呼び出しで実装できそう。

実装

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Combination1 {
    // 候補となるリストと、何個ピックアップするかを渡す
    public static List<List<Integer>> make (List<Integer> candidate, int r) {
        // 5C6みたいなのは空
        // 0C5も空
        // 5C0も空
        if (candidate.size() < r || candidate.size() <= 0 || r <= 0) {
            List<List<Integer>> empty = new ArrayList<>();
            empty.add(new ArrayList<>());
            return empty;
        }

        List<List<Integer>> combination = new ArrayList<>();
        // 5C3だったら、添字0, 1, 2だけ考えたらいい
        for (int i = 0; i <= candidate.size() - r; i++) {
            // 一つ取り出して
            Integer picked = candidate.get(i);
            List<Integer> rest = new ArrayList<>(candidate);
            // 以降の文字を削って
            rest.subList(0, i + 1).clear();
            // 再帰呼び出しし、得られたリストの全ての先頭に取り出したものを結合する
            combination.addAll(make(rest, r - 1).stream().map(list -> {
                list.add(0, picked);
                return list;
            }).collect(Collectors.toList()));
        }
        return combination;
    }
}

条件周り、もう少し綺麗にできそうだけど、まあ考え方はあってそうなので、このままにしておく。

まとめ

今回の組み合わせアルゴリズムは、自分で考えたのを実装したらとりあえず作ることが出来た。順列生成アルゴリズムを自分で実装してみたので考えついたと考えると、やはり自分で実装しておくのは大事だなーと思った。

これまでの学習

Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1) - $shibayu36->blog;