从n个数字选出m个数字的组合
1.递归方法一
代码如下：
public class MathCombine {
/**
* @param args
*/
public static void main(String[] args) {
int array[]={11,22,33,44,55};
int [][] ret=getCombine(array.length,3);
if(null!=ret)
{
System.out.println("组合顺序如下:");
for (int j = 0; j < ret.length; j++)
{
for (int j2 = 0; j2 < ret[j].length; j2++)
{
System.out.print("["+(j2+1)+"]="+(ret[j][j2]+1)+";");
}
System.out.print("\n");
}
System.out.println("\n组合结果如下:");
for (int j = 0; j < ret.length; j++)
{
System.out.print("{");
for (int j2 = 0; j2 < ret[j].length; j2++)
{
System.out.print(array[ret[j][j2]]+((j2==ret[j].length-1)?"":","));
}
System.out.print("}\n");
}
}
}
/**
* 最原始递归方法
* 1.从前面的m个位置移动到末尾(如:11100移动到00111)
* 2.其中前面m位的移动条件分别是小于(n-m)...(n-2),(n-1),n;
* 3.当条件2发生时(当0-m个位置,假设p)，需要考虑p-1的取值，P+1以及以后的取值
*/
public static int[][] getCombine(int n, int m)
{
if(m <=0 || m>n)
{
return null;
}
else
{
int count=getallCombineCount(n,m);
int [][] ret=new int[count][m];
int index=0;
int []indexArray=new int[m];
for (int i = 0; i < indexArray.length; i++)
{
indexArray[i]=i;
ret[index][i]=i;
}
boolean isBreak=false;
while(!isBreak)
{
for (int i = m-1; i >= 0; i--)
{
int nextValue = indexArray[i] + 1;
if(nextValue > i+(n-m))//其中i+(n-m)表示i位置处允许的最大索引值
{
if(i-1>= 0)
{
int preValue=indexArray[i-1]+1;
if(preValue>i+(n-m)-1)
{
continue;
}
else
{
indexArray[i-1]=preValue;
for (int j = i; j < m; j++)
{
if (j == m-1 )
{
indexArray[j]=indexArray[j-1];
}
else
{
indexArray[j]=indexArray[j-1]+1;
}
}
break;
}
}
else
{
isBreak=true;
break;
}
}
else//满足条件
{
indexArray[i]=nextValue;
index++;
for (int j = 0; j < indexArray.length; j++)
{
ret[index][j]=indexArray[j];
}
break;
}
}
if(index>=count-1)
{
isBreak=true;
}
}
return ret;
}
}
/**
* 获取组合总数
* @param n
* @param m
* @return
*/
public static int getallCombineCount(int n, int m)
{
return getAllCount(n,m)/getFactorial(m);
}
/**
* 总数量
* @param m
* @return
*/
public static int getAllCount(int n,int m)
{
int ret=1;
for (int i = 0; i < m; i++)
{
ret*=n;
n--;
}
return ret;
}
/**
* 阶乘
* @param m
* @return
*/
public static int getFactorial(int m)
{
return m*(m>1?getFactorial(m-1):1);
}
}
打印结果如下：
2.递归方法二
代码如下：
public class MathCombine2 {
/**
* @param args
*/
public static void main(String[] args) {
int array[]={11,22,33,44,55};
int [][] ret=getCombine2(array.length,3);
if(null!=ret)
{
System.out.println("组合顺序如下:");
for (int j = 0; j < ret.length; j++)
{
for (int j2 = 0; j2 < ret[j].length; j2++)
{
System.out.print("["+(j2+1)+"]="+(ret[j][j2]+1)+";");
}
System.out.print("\n");
}
System.out.println("\n组合结果如下:");
for (int j = 0; j < ret.length; j++)
{
System.out.print("{");
for (int j2 = 0; j2 < ret[j].length; j2++)
{
System.out.print(array[ret[j][j2]]+((j2==ret[j].length-1)?"":","));
}
System.out.print("}\n");
}
}
}
/**
* 首先从n个数中选取编号最大的数，然后在剩下的n-1个数里面选取m-1个数，直到m-1为1为止。
* @param n
* @param m
* @return
*/
public static int[][] getCombine2(final int n , final int m)
{
if(m <=0 || m>n)
{
return null;
}
else
{
int count=getallCombineCount(n,m);
final int [][] ret=new int[count][m];
Runnable mCombineRunnable=new Runnable() {
int index=0;
int []arrayIndex=new int[m];
@Override
public void run() {
index=0;
arrayIndex=new int[m];
getCombine2Data(n,m,arrayIndex);
}
public void getCombine2Data(int n , int m ,int[]arrayIndex)
{
for (int i = n; i >= m; i--)
{
arrayIndex[m-1]=i-1;
if(m>1)
{
getCombine2Data(i-1,m-1,arrayIndex);
}
else
{
for(int k = arrayIndex.length-1;k>=0;k--)
{
ret[index][arrayIndex.length-k-1]=arrayIndex[k];
}
index++;
}
}
}
};
mCombineRunnable.run();
mCombineRunnable=null;
return ret;
}
}
/**
* 获取组合总数
* @param n
* @param m
* @return
*/
public static int getallCombineCount(int n, int m)
{
return getAllCount(n,m)/getFactorial(m);
}
/**
* 总数量
* @param m
* @return
*/
public static int getAllCount(int n,int m)
{
int ret=1;
for (int i = 0; i < m; i++)
{
ret*=n;
n--;
}
return ret;
}
/**
* 阶乘
* @param m
* @return
*/
public static int getFactorial(int m)
{
return m*(m>1?getFactorial(m-1):1);
}
}
打印结果如下：
