同じものを含む数珠順列の問題をJavaで解いてみた。

　同じものを含む数珠順列(重複数珠順列)の問題をJavaでプログラムを作って解いてみました。(^_^;

白玉が４個、黒玉が３個、赤玉が１個あると、これらの玉をひもに通し輪にする方法

●NecklacePerm01.java

/*
 * NecklacePerm01.java
 * 
 */

import java.util.Arrays;

class NecklacePerm01 {
    static boolean next_perm(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 strRev(String s) {
        char[] c=s.toCharArray();
        char t;
        
        for(int i=0, j=s.length()-1; i< j; i++,j--){
            t=c[i]; c[i]=c[j]; c[j]=t;  // swap(c,i,j);
        }
        return(new String(c));
    }
    
    public static void main(String[] args) {
        final String P="白白白白黒黒黒赤";
        final int N=P.length();
        final int R=N;
        char[] p=P.toCharArray();       // 順列生成用
        String s="";
        
        long tm=System.nanoTime();      // Timer Start
        int count=0;
        
        Arrays.sort(p);
        do{
            String t=new String(p);
            if(!s.contains(t)){
                 count++;
                 //System.out.println(t);
                 int n=t.indexOf("赤");
                 System.out.println(t.substring(n)+t.substring(0,n));
                 s+=t+t+"|";
                 t=strRev(t);
                 s+=t+t+"|";
            }
        }while(next_perm(p,N,R));
        System.out.println("計: "+count);
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

赤黒黒黒白白白白
赤黒黒白白白白黒
赤白黒黒黒白白白
赤黒白黒黒白白白
赤黒黒白黒白白白
赤黒黒白白白黒白
赤黒白白白黒白黒
赤白黒黒白白白黒
赤白白黒黒黒白白
赤白黒白黒黒白白
赤白黒黒白黒白白
赤黒白白黒黒白白
赤黒白黒白黒白白
赤黒黒白白黒白白
赤黒白白黒白白黒
赤白黒黒白白黒白
赤黒白黒白白黒白
赤黒白白黒白黒白
赤白黒白黒白黒白
計: 19
Runtime : 0.012 [sec]

※参考URL
●同じものを含む円順列と数珠順列