知恵袋の条件つき同じものを含む順列の問題を解いてみた。

Java

　知恵袋の条件つき同じものを含む順列の問題を解いてみました。(^_^;

　九個の文字A,A,B,B,B,C,C,C,Cを一列に並べるものとする。
(1)異なる並べ方の総数
(2)Aが連続して並ぶ並べ方
(3)Cが2個以上連続して並ばない並べ方のうち、先頭がCである並べ方
(4)Cが2個以上 連続して並ばない並べ方

● PermSameWithCond1.java

/* 
 * PermSameWithCond1.java
 */

class PermSameWithCond1 {
    // 順列生成
    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);
    }
    
    public static void main(String[] args){
        final String P = "AABBBCCCC";
        final int N = P.length();
        char[] p = P.toCharArray();
        int iCnt1 = 0, iCnt2 = 0, iCnt3 = 0, iCnt4 = 0;
        
        long tm=System.nanoTime();      // Timer Start
        do{
            iCnt1++;
            String s = new String(p);
            if(s.contains("AA")) iCnt2++;
            if(!s.contains("CC")){
                 iCnt4++;
                 if(p[0]=='C') iCnt3++;
            }
        } while(nextPerm(p,N,N));
        System.out.println("(1) "+iCnt1);
        System.out.println("(2) "+iCnt2);
        System.out.println("(3) "+iCnt3);
        System.out.println("(4) "+iCnt4);
        
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

(1) 1260
(2) 280
(3) 100
(4) 150
Runtime : 0.003 [sec]