组合算法的实现
从m个中取n个的算法。 最容易理解的是递归，但其效率太低了。
实现方法1 :
//组合算法
//本程序的思路是打开一个数组，其下标表示从1到n的个数，数组元素的值为1表示其下标
//代表的数量被选中，0的情况下没有被选中。
//首先初始化，将数组的前m个元素放在1上，指示第一个组合是前n个。
//然后从左向右扫描数组元素值“10”的组合，找到第一个“10”的组合并将其
//在组合“01”的同时，将其左侧的所有“1”移动到数组的最左端。
//最初的“1”移动到数组的n-m的位置，即m个“1”全部移动到右端时
//到了最后的组合。
//例如求出从5中选择3的组合：
//11100//1，2，3
//11010//1，2，4
//10110//1，3，4
//01110//2，3，4
//11001//1，2，5
//10101//1，3，5
//01101//2，3，5
//10011//1，4，5
//01011//2，4，5
//00111//3，4，5
importjava.util.ArrayList；
importjava.util.List；
//*
*面试遇到的问题是在网上查找资料，加上自己的总结，实现java代码组合的算法
*从n个中提取m个的组合为n*(n-1 )n-m1 )/m * (m-1 )……2*1该方法容易理解，但具体算法分析困难。
*
*@date
*@author
*
*/
classZuhe{
//*
*@parama:组合数组
*@paramk:生成组合个数
*@return:所有可能的组合数组列表
*/
privatelistzuhe(int[]a，intm ) {
Zuhe1zuhe=newZuhe1(；
列表列表=new ArrayList (；
intn=a.length；
布尔标志=假； //是否为最后组合的标记
//生成辅助数组。 首先，将数组的前m个元素放在1上，指示第一个组合是前m个。
int[]tempNum=newint[n]；
for(inti=0； I
if(I )
tempNum[i]=1；
}else{
tempNum[i]=0；
}
system.out.print(tempnum[I]；
}
打印(tempnum； //打印辅助排列
list.add(zuhe.createresult(a，tempNum，m ) )； //打印第一的默认组合
do{
intpose=0； //记录改变的位置
intsum=0； //记录变更位置左侧1的个数
//然后从左向右扫描数组元素值“10”的组合，找到第一个“10”的组合并设为“01”
for(inti=0； I
if(tempnum[I]==1tempnum[I1]==0) {
tempNum[i]=0；
tempNum[i 1]=1；
pose=i；
布雷克；
}
}
打印(tempnum； //打印辅助排列
list.add(zuhe.createresult(a，tempNum，m ) )； //打印第一的默认组合
//同时将其左侧的“1”全部移动到数组的最左端。
for(inti=0； I
if(tempnum[I]==1) ) ) ) )。
sum；
}
for(inti=0； I
if(I )
tempNum[i]=1；
else
tempNum[i]=0；
}
//判断是否为最后一个组合：当第一个“1”位于数组的n-m位置，即m个“1”全部移动到右端时，得到最后一个组合。
flag=false；
for (
int i = n - m; iif (tempNum[i] == 0)
flag = true;
}
} while (flag);
return list;
}
// 根据辅助数组和原始数组生成 结果数组
public int[] createResult(int[] a, int[] temp, int m) {
int[] result = new int[m];
int j = 0;
for (int i = 0; i
if (temp[i] == 1) {
result[j] = a[i];
System.out.println("result[" + j + "]:" + result[j]);
j++;
}
}
return result;
}
// 打印
public void print1(List list) {
for (int i = 0; i
System.out.println();
int[] temp = (int[]) list.get(i);
for (int j = 0; j
System.out.print(temp[j] + " ");
}
}
}
// 打印整数数组的方法
public void print(int[] a) {
System.out.println("生成的辅助数组为：");
for (int i = 0; i
System.out.print(a[i]);
}
System.out.println();
}
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5 }; // 整数数组
int m = 3; // 待取出组合的个数
Zuhe1 zuhe = new Zuhe1();
List list = zuhe.zuhe(a, m);
zuhe.print1(list);
}
}
实现方法二：使用递归算法，但比较难于理解，摘自网上，慢慢消化
/**
* 从n个数里取出m个数的组合是n*(n-1)*...*(n-m+1)/m*(m-1)*...2*1
*/
import java.io.*;
public class Test1 {
public static void main(String[] args) {
select(2);
}
private static void select(int k) {
char[] result = new char[k];
subselect(0, 1, result, k);
}
private static void subselect(int head, int index, char[] r, int k) {
for (int i = head; i
if (index
r[index - 1] = a[i];
System.out.println("i="+(i)+";index="+(index));
subselect(i + 1, index + 1, r, k);
} else if (index == k) {
r[index - 1] = a[i];
System.out.println(";i="+(i)+";index="+(index)+";index==k:"+(index==k));
System.out.print(i+"===");
System.out.println(r);
subselect(i + 1, index + 1, r, k);
} else {
System.out.println("++");
return;//返回到何处？奇怪
}
}
}
private static char[] a = { 'a', 'b', 'c' };
}