知恵袋で見つけた赤玉と白玉の組分けの問題をJavaで解いてみた。(2)

　知恵袋の赤玉と白玉の組分け問題をJavaで解いてみました。

赤玉が１０個、白玉が９０個、計１００個の玉をA,B,C,Dのボックスに１０個ずつ分ける。同じ色の玉は区別しないとして、玉の入れ方は何通りあるか。

　直接、同じものを含む順列を生成させて求めようとしましたが、100とか40とか、ちょっと無理っぽいので、数学的な解法をちょっと取り入れて、'r'の0から10個と仕切り'|'3個の同じものを含む順列の合計で求めてみました。(^_^;
　ちなみに、Pythonでもやってみましたが、rが8個目ぐらいから急に減速するので途中で諦めました。(^_^;

● RWBalls1.java

/* 
 * RWBalls1.java
 */

public class RWBalls1 {
    // 順列生成
    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 String strDup(String s, int n) {
        String r = "";
        for(int i=0; i< n; i++)
            r += s;
        return r;
    }
    
    public static void main(String[] args) {
        int total = 0;
        
        long tm=System.nanoTime();      // Timer Start
        for (int i = 0; i<=10; i++){
            String P = strDup("r",i)+"|||";
            char[] p = P.toCharArray();
            int n = P.length();
            int subTotal = 0;
            do{
                total++;
                subTotal++;
            }while(nextPerm(p,n,n));
            System.out.printf("%13s :  %3d\n", P, subTotal);
        }
        System.out.printf("         合計 : %4d\n", total);
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

          ||| :    1
         r||| :    4
        rr||| :   10
       rrr||| :   20
      rrrr||| :   35
     rrrrr||| :   56
    rrrrrr||| :   84
   rrrrrrr||| :  120
  rrrrrrrr||| :  165
 rrrrrrrrr||| :  220
rrrrrrrrrr||| :  286
         合計 : 1001
Runtime : 0.026 [sec]

※参考URL
●知恵袋で見つけた赤玉と白玉の組分けの問題をJavaで解いてみた。

明解Java 入門編