知恵袋の名刺の取り方の問題をJavaで解いてみた。

Java

　知恵袋の名刺の取り方の問題をJavaで解いてみました。

「A,B,C,D,Eの５人の名刺が１枚ずつある。この５人が１枚ずつ名刺を取るとき、１人だけが自分の名刺を取るような取り方は何通りあるか。」

　これは、完全順列の応用問題のようです。(^_^;
※参考URL
●完全順列
　そういえば、今日で、250日目です。金市民まで、もう一息です。o(^-^)o

● CallingCard1.java

/* 
 * CallingCard1.java
 */

class CallingCard1 {
    // 順列生成
    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 NAME = "ABCDE";
        char[] card = NAME.toCharArray();   // 名刺
        final int N = NAME.length(), R = N;
        int count=0;
        
        long tm=System.nanoTime();      // Timer Start
        do{
            int subTotal=0; // 小計
            for(int i=0; i< N; i++)
                if(card[i]==NAME.charAt(i)) subTotal++;
            if(subTotal==1){
                count++;
                // System.out.println(new String(card));
            }
        } while(nextPerm(card,N,R));
        System.out.println("count="+count);
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

count=45
Runtime : 0.001 [sec]