重複組合せの、負でない整数解の個数の問題をJavaで解いてみた。

　知恵袋の重複組合せの、負でない整数解の個数の問題をJavaで解いてみました。(^_^;

方程式ｘ＋ｙ＋ｚ＝１０の負でない整数解は何組あるか

　仕切り(I)と丸(O)の順列を生成し、それをカウントして求めてみました。(^_^;
　ちなみに、

●HomogeneousProduct.java

/*
 * HomogeneousProduct.java
 */

import java.util.Arrays;

class HomogeneousProduct {
    // 順列生成
    static boolean nextPerm(char[] p, int n, int r) {
        int i, j;
        char t;
        
        if(r <= 0 || n < r) return(false);
        for(i = r + 1; i <= n-1; i++)
            for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p,j,j-1);
            }
        for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
        if(i==0) return(false);
        for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
        t = p[j]; p[j] = p[i-1]; p[i-1] = t;            // swap(p,j,i-1);
        for(j = n - 1; i < j; i++, j--){
            t = p[i]; p[i] = p[j]; p[j] = t;            // swap(p,i,j);
        }
        return(true);
    }
    // 重複組合せ生成
    static boolean nextHomoPro(int[] h, int n, int r) {
        int i,j, k = n+r-1;
        String s="";
        
        for(i=0; i< n; i++){
            s+="I";
            for(j=0; j< h[i]; j++) s+="O";
        }
        s=s.substring(1);
        //System.out.println(s);
        char[] p = s.toCharArray();
        if(!nextPerm(p,k,k)) return(false);
        //System.out.println(new String(p));
        s=new String(p)+"I";
        for(i=0; i< n; i++){
            h[i]=(j=s.indexOf("I"));
            s=s.substring(j+1);
        }
        return(true);
    }
    
    public static void main(String[] args) {
        int[] h = {0,0,10};
        int cnt=0;
        long tm=System.nanoTime();      // Timer Start
        
        do{
            System.out.println((++cnt)+" : "+Arrays.toString(h));
        }while(nextHomoPro(h,3,10));
        
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

1 : [0, 0, 10]
2 : [0, 1, 9]
3 : [0, 2, 8]
…(省略)…
64 : [9, 0, 1]
65 : [9, 1, 0]
66 : [10, 0, 0]
Runtime : 0.045 [sec]

新課程チャート式基礎からの数学1+A