Statistic Utility

This class is used to generate A(m,n) and C(m,n) series

/**
 * Created by luncrzs on 16/1/27.
 */

/**
* Stats is a class that generate sequence of statistical function A(m,n) and C(m,n) where
* A(m,n) takes n objects from m objects in an order-sensitive case and C(m,n) takes n 
* objects from m objects in an order-insensitive case.
*/
public class Stats {

    /**
     * Example method to illustrate the usage of this class
     *
     * @param args
     */
    public static void main(String[] args){
        Stats stats = new Stats();
        int[][] results = stats.A(8,2);
        for(int i=0; i<results.length; i++){
            for(int j=0; j<results[i].length;j++){
                System.out.print(results[i][j]+" ");
            }
            System.out.print("\n");
        }
    }

    /**
     * A method used to calculate factorial of positive integer n
     *
     * @param n
     * @return facorial of n, aka n!
     */
    public static long factorial(int n){
        int result = 1;
        for(int i=1; i<=n; i++){
            result *= i;
        }
        return result;
    }

    /**
     * A method used to calculate how many possible arrangement are there
     * for C(m,n). Should be m!/(n!*(m-n)!)
     *
     * @param m how many objects are taken from
     * @param n how many objects are taken
     * @return how many possible arrangement are there
     */
    public static int cCount(int m, int n){
        // m should be larger than n
        if(m<n){
            return 0;
        }

        // When calculate C(200,198), factorial of 198 can be very large so transform
        // C(200,198) to C(200,2) which have the same number of arrangments
        if(n>m-n){
            return cCount(m,m-n);
        }

        long count = 1;

        // m!/(n!*(m-n)!) can be simplified to continuous multiplication from m-n+1 to m
        for(int i=m-n+1; i<=m; i++){
            count *= i;
        }
        return (int)(count/factorial(n));
    }

    /**
     * A method used to calculate how many possible arrangement are there
     * for A(m,n). Should be m!/(m-n)!
     *
     * @param m how many objects are taken from
     * @param n how many objects are taken
     * @return how many possible arrangement are there
     */
    public static int aCount(int m, int n){
        if(m<n){
            return 0;
        }
        int result = 1;
        for(int i=m; i>m-n; i--){
            result *= i;
        }
        return result;
    }

    int now = 0; // indicate which array index the calculation is in currently
    int[][] result; // result array used to storage possible sequence

    /**
     * This method is used to calculate statistical function C(m,n)
     *
     * @param m how many objects are taken from
     * @param n how many objects are taken
     * @return sequence of possible arrangements
     */
    public int[][] C(int m, int n){
        int count = cCount(m,n);
        result = new int[count][n];
        now = 0;

        proceedC(m,n,0,0); // recur to calculate the results

        return result;
    }

    /**
     * This method is recursion method that is used to calculate all
     * possible arrangments of function C(m,n)
     * @param m how many objects are taken from
     * @param n how many objects are taken
     * @param start the smallest object index that we are calculating
     * @param level at which index we are calculating in a possible arrangement
     */
    private void proceedC(int m, int n, int start, int level){
        if(n-level==1){ // Calculating last element in an arrangement,
            for(int i=start; i<m; i++){
                if(now+1<result.length){
                    for(int j=0; j<level; j++){
                        result[now+1][j] = result[now][j];
                    }
                }
                result[now++][level] = i; // Move to next possible arrangement
            }
        }else{ //Calculating middle element in an arrangement
            for(int i=start; i<m-n+level+1; i++){
                result[now][level] = i;
                proceedC(m,n,i+1,level+1);
            }
        }
    }

    /**
     * This method is used to calculate statistical function A(m,n)
     *
     * @param m how many objects are taken from
     * @param n how many objects are taken
     * @return sequence of possible arrangements
     */
    public int[][] A(int m, int n){
        int count = aCount(m,n);
        result = new int[count][n];
        now = 0;

        proceedA(m,n,0); // recur to calculate the results

        return result;
    }

    /**
     * This method is recursion method that is used to calculate all
     * possible arrangments of function A(m,n)
     * @param m how many objects are taken from
     * @param n how many objects are taken
     * @param level at which index we are calculating in a possible arrangement
     */
    private void proceedA(int m, int n, int level){
        if(n-level==1){ // Calculating last element in an arrangement,
            for(int i=0; i<m; i++){
                if(now==result.length){
                    break;
                }
                boolean skip = false;
                for(int k=0; k<level; k++){
                    if(i==result[now][k]){
                        skip = true; // we cannot take repeating object
                    }
                }
                if(skip){
                    continue;
                }
                if(now+1<result.length){
                    for(int j=0; j<level; j++){
                        result[now+1][j] = result[now][j];
                    }
                }
                result[now++][level] = i; // Move to next possible arrangement
            }
        }else{ //Calculating middle element in an arrangement
            for(int i=0; i<m; i++){
                if(now==result.length){
                    break;
                }
                boolean skip = false;
                for(int k=0; k<level; k++){
                    if(i==result[now][k]){
                        skip = true;
                    }
                }
                if(skip){
                    continue;
                }
                result[now][level] = i;
                proceedA(m,n,level+1);
            }
        }
    }
}

标签: java, utility

添加新评论