組合せ生成プログラムの応用 - Java

　組合せ生成プログラムの応用として、Javaで確率の問題を解いてみました。(^_^;

xy平面上の16個の点の集合｛（x、y）|x＝0、1、2、3 y＝0、1、2、3｝を考える。
この集合から異なる３点を無作為に選ぶ試行において、事象「選んだ３点が三角形の頂点となり、その三角形の面積は9/2である」の起こる確率を求めよ。

　点は、n=0〜15の整数値で与えて、n/4でｙ座標、n%4でｘ座標を得ています。三角形の面積の2倍というのは、整数のまま扱いたかったからで、参考URLの行列式を使った公式で面積を求めています。
　JavaScriptの組合せ生成プログラムをJavaに翻訳しておきました。(^_^;
　ちなみに、next_combメソッドは、毎回、初期設定し直しているので、クラスを作って、コンストラクタではじめに1回だけ初期設定するようにすると、倍速ぐらいになります。(^_^;

●Probability.java

import java.util.Arrays;
public class Probability {
    // 三角形の面積の2倍を求める
    static int biAreaOfTriangle(int[] p){
        int x1=p[0]%4, x2=p[1]%4, x3=p[2]%4;
        int y1=p[0]/4, y2=p[1]/4, y3=p[2]/4;
        return (Math.abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)));
    }
    
    // 最大公約数
    static int gcd(int a, int b){
        return( b == 0 ? a : gcd(b, a % b) );
    }

    static void swap(int[] s, int i, int j) {
        int t = s[i]; s[i] = s[j]; s[j] = t;
    }
    
    // 順列生成
    static boolean next_perm(int[] p, int n, int r) {
        int i, j, k;
        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--)
                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--);
        swap(p,j,i-1);
        for(k = 0; k <= (n-i-1)/2; k++)
            swap(p,i+k,n-k-1);
        return(true);
    }
    
    // xがa[]の何番目にあるか調べる関数
    static int get_pos(int[] a, int x) {
        for(int i=0; i< a.length; i++)
            if(a[i]==x) return(i);    // あるときは、0〜a.length-1を返す. 
        return(-1);                   // ないときは、-1を返す. 
    }
    
    // 組合せ生成
    static boolean next_comb(int[] c, int n, int r) {
        int i, j, k;
        if(r<= 0 || n< r) return(false);
        
        int[] o=new int[n];
        int[] p=new int[n];

        o=Arrays.copyOf(c,c.length);
        Arrays.sort(o);
        for(i=0; i< n; i++) p[i]=1;
        for(i=0; i< r; i++)
            p[get_pos(o,c[i])]=0;

        boolean res=next_perm(p, n, n);
        if(!res) n=0;
        for(i=j=0, k=r; i< n; i++)
            if(p[i]==0) c[j++]=o[i]; else c[k++]=o[i];
        //delete o,p; // Javaでは不要
        return(res);
    }
    
    public static void main(String[] args) {
        final int N=16;
        final int R= 3;
        int[] p=new int[N];
        for(int i=0; i< N; i++) p[i]=i;
        int count=0, total=0;
        
        long tm=System.currentTimeMillis();    // Timer Start
        do{
            //System.out.println(Arrays.toString(p));
            total++;             // すべての場合をカウント
            int s=biAreaOfTriangle(p);
            if(s==9) count++;    // 題意を満たす場合のみをカウント
        }while(next_comb(p,N,R));
        int g;
        if(count!=0) g=gcd(count, total); else g=1;
        System.out.println("p="+(count/g)+"/"+(total/g));
        
        tm=System.currentTimeMillis()-tm;    // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1000.0);
    }
}

●実行結果

p=3/140
Runtime : 0.006 [sec]

P.S.
　ちなみに、組合せ生成 next_comb メソッドを次のように書き換えると、get_pos メソッドが不用になります。o(^-^)o

● Probability1.java

/* 
 * Probability1.java
 */

public class Probability1 {
    // 順列生成
    static boolean nextPerm(int[] p, int n, int r) {
        int i, j;
        int 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 nextComb(int[] p, int n, int r) {
        int i;
        do{
            if(!nextPerm(p,n,r)) return(false);
            for(i = 0; i< r-1; i++)
                if(p[i]> p[i+1]) break;
        } while (i< r-1);
        return(true);
    }
    // 三角形の面積の2倍を求める
    static int biAreaOfTriangle(int[] p){
        int x1 = p[0]%4, x2 = p[1]%4, x3 = p[2]%4;
        int y1 = p[0]/4, y2 = p[1]/4, y3 = p[2]/4;
        return Math.abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));
    }
    // 最大公約数
    static int gcd(int a, int b){ return (b==0) ? a : gcd(b, a % b); }
    
    public static void main(String[] args) {
        final int N = 16, R =  3;
        int[] p = new int[N];           // 組合せ生成用
        for(int i = 0; i< N; i++) p[i]=i;
        int count = 0, total = 0;
        
        long tm = System.nanoTime();    // Timer Start
        do{
            if(biAreaOfTriangle(p)==9) count++;
            total++;
        }while(nextComb(p,N,R));
        int g = (count!=0) ? gcd(count,total) : 1;
        System.out.println("p = "+(count/g)+"/"+(total/g));
        tm = System.nanoTime()-tm;      // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}