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);
}
}
}
}