山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

重複のないn個の数字からr個選び出力する [組み合わせの列挙]

組み合わせの列挙

 n 個の数字から r 個選ぶ時の数字の組み合わせは、 _n \mathrm{C} _r 通りあります。その組み合わせを列挙するには再帰を使うことが考えられます。

f:id:yamakasa3:20180710210825p:plain

import java.util.Arrays;

public class Test {
    static int []a;
    static int sum = 0;
    public static void main(String[] args) {
        int n = 4;
        a = new int[n];
        Arrays.fill(a, 0);
        comb(1, 2);
    }
    static void comb(int m, int r) {
        int n = a.length;
        if(n == r) {
            for(int i = 0; i < n; i++) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }else if(n < r){
            System.out.println("エラー");
            System.exit(0);
        }
        if(m <= r) {
            int k = a[m - 1] + 1;
            for(int i = k; i <= n - r + m; i++){
                a[m] = i;
                comb(m + 1, r);
            }
        }
        else {
            for(int i = 1; i <= r; i++){
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
     }
}

参考サイト

組み合わせ