読者です 読者をやめる 読者になる 読者になる

なんとな~くしあわせ?の日記

ClojureとかAWSの設定とかをメモする技術ブログ

Javaで簡単な組み合わせの総数 nCr を求めてみる



Aizu Online Judgeをやっていて、求められんかな?と思ったので。
速さとかは遅いと思う。

ソースコード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.HashSet;

public class prog {

    public static void main(String[] args) {

        // nCr : n=[1,2,3,4,5],r=3 で試してみる
        ArrayList<Integer> n1 = new ArrayList<>(Arrays.asList(1,2,3,4,5));
        //getCombination(n1,3);

        // nCr : n=[1,2,3,4,5,6,7],r=4 で試してみる
        ArrayList<Integer> n2 = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7));
        getCombination(n2,4);
    }

    private static Set<ArrayList<Integer>> getCombination(ArrayList<Integer> n, Integer r) {
        Set<ArrayList<Integer>> ans = new HashSet<ArrayList<Integer>>();
        combination(n, r, ans);
        for (ArrayList<Integer> e : ans) {
            System.out.println(e.toString());
        }
        return ans;
    }

    private static void combination(ArrayList<Integer> n, Integer r, Set<ArrayList<Integer>> ans) {
        if (n.size() == r) {
            ans.add(n);
            return;
        }
        for (int i = 0; i < n.size(); i++) {
            ArrayList<Integer> N = new ArrayList<Integer>();
            N.addAll(n);
            N.remove(i);
            combination(N,r,ans);
        }
    }
}

所感

再帰関数は苦手で、自分でも若干どうして動いてるのかわからない部分がある。手続き型の設計書にしろと言われると多分無理(やめたほうがいい)。しかしポイントは以下で、与えられたサイズの配列からremoveで削除して組み合わせを作っているのだが、削除するインデックスがiで徐々にインクリメントされるのでn回試行するといろいろな組み合わせができる。

        for (int i = 0; i < n.size(); i++) {
            ArrayList<Integer> N = new ArrayList<Integer>();
            N.addAll(n);
            N.remove(i);
            combination(N,r,ans);
        }

あと、答えの型は

Set<ArrayList<Integer>>

にしておくと、勝手に配列の重複削除されるのです。nCrじゃなくてn-r+1Crを求めたい場合は、SetじゃなくてただのListにすればよいのでは。

答え合わせはこのへんで
組合せ - 高精度計算サイト