组合算法实现
从m个数里面取n个数的算法。最容易理解的就是递归,但是其效率太低。
实现方法一:
// 组合算法
// 本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标
// 代表的数被选中,为0则没选中。
// 首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
// 然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为
// “01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
// 当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得
// 到了最后一个组合。
// 例如求5中选3的组合:
// 1 1 1 0 0 //1,2,3
// 1 1 0 1 0 //1,2,4
// 1 0 1 1 0 //1,3,4
// 0 1 1 1 0 //2,3,4
// 1 1 0 0 1 //1,2,5
// 1 0 1 0 1 //1,3,5
// 0 1 1 0 1 //2,3,5
// 1 0 0 1 1 //1,4,5
// 0 1 0 1 1 //2,4,5
// 0 0 1 1 1 //3,4,5
import java.util.ArrayList;
import java.util.List;
/**
* 面试中遇到的问题,在网上查找资料,加上自己的总结, java 代码实现组合的算法
* 从n个数里取出m个数的组合是n*(n-1)*...*(n-m+1)/m*(m-1)*...2*1 该方法比较好理解,但具体算法的分析却有难度。
*
* @date
* @author
*
*/
class Zuhe1 {
/**
* @param a:组合数组
* @param k:生成组合个数
* @return :所有可能的组合数组列表
*/
private List zuhe(int[] a, int m) {
Zuhe1 zuhe = new Zuhe1();
List list = new ArrayList();
int n = a.length;
boolean flag = false; // 是否是最后一种组合的标记
// 生成辅助数组。首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
int[] tempNum = new int[n];
for (int i = 0; i < n; i++) {
if (i < m) {
tempNum[i] = 1;
} else {
tempNum[i] = 0;
}
System.out.print(tempNum[i]);
}
print(tempNum);// 打印辅助数组
list.add(zuhe.createResult(a, tempNum, m));// 打印第一中默认组合
do {
int pose = 0; // 记录改变的位置
int sum = 0; // 记录改变位置 左侧 1 的个数
// 然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”
for (int i = 0; i < (n - 1); i++) {
if (tempNum[i] == 1 && tempNum[i + 1] == 0) {
tempNum[i] = 0;
tempNum[i + 1] = 1;
pose = i;
break;
}
}
print(tempNum);// 打印辅助数组
list.add(zuhe.createResult(a, tempNum, m));// 打印第一中默认组合
// 同时将其左边的所有“1”全部移动到数组的最左端。
for (int i = 0; i < pose; i++) {
if (tempNum[i] == 1)
sum++;
}
for (int i = 0; i < pose; i++) {
if (i < sum)
tempNum[i] = 1;
else
tempNum[i] = 0;
}
// 判断是否为最后一个组合:当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得到了最后一个组合。
flag = false;
for (int i = n - m; i < n; i++) {
if (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 < a.length; 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 < list.size(); i++) {
System.out.println();
int[] temp = (int[]) list.get(i);
for (int j = 0; j < temp.length; j++) {
System.out.print(temp[j] + " ");
}
}
}
// 打印整数数组的方法
public void print(int[] a) {
System.out.println("生成的辅助数组为:");
for (int i = 0; i < a.length; 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 < a.length + index - k; i++) {
if (index < k) {
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' };
}
分享到:
相关推荐
6位数,共有几种排列组合的算法,java实现
排列组合算法实现,支持模板类。支持重复数的排列。算法采用递归方法,简单易懂。
本资源附带文档解释了排列组合算法的实现和原理。其中排列算法是基于递归实现的,组合算法是基于高效的位移法实现的。代码是使用Java版实现的。
排列组合 排列 组合 java排列组合算法 排列组合算法
Java排列组合算法 - 郭睿的专栏 - CSDN博客Java排列组合算法 - 郭睿的专栏 - CSDN博客
Java排列组合算法
Java排列组合_组合算法,利用list及set的无序性, 通过递归实现,不同于以往的排列组合 自娱自乐
此外,文档还提供了各种排列组合算法的详细代码示例和实现细节,包括递归和迭代方法。文档还涵盖了高级主题,如如何计算有重复元素的排列组合数量,以及如何优化这些算法的性能。 无论您是Java编程的初学者还是有...
介绍了几种用JAVA实现的排列组合算法,有需要的朋友可以参考一下
所使用的算法应该是效率最高的算法,而且这两个类都只是对需要排列组合的数组的下标进行处理,所以能对任何类型的数组进行排列组合。
用java语言写的组合数学中生成排列算法的代码,并由界面
这是算法课老师叫我们做的一个算法作业,我是按照他说的写的,如果自己写的话完全用不着那么多行,呵呵。
阶乘与排列组合算法!在各行各业都能用得到的,比较彩票业,以及复杂的生产环境预测等软件开发
主要为大家详细介绍了高效的java版排列组合算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
主要介绍了Java实现字符数组全排列的方法,涉及Java针对字符数组的遍历及排序算法的实现技巧,需要的朋友可以参考下
主要介绍了Java获得一个数组的指定长度排列组合算法,结合实例形式分析了java排列组合相关数组遍历、运算操作技巧,需要的朋友可以参考下
实现了排列组合算法的类(JAVA),实现了排列组合算法的类(JAVA)
该资源为本人自己写的交叉组合算法代码的工具类,一共两个,搭配文章看效果更好!
今天 写了一个java小程序 是将a,b,c,d,e,f,g这7个字母的全排列打印出来,排除a,d相邻的情况 算然很简单 但是我用递归调用的方式写的 算法还是很不错的 建议新手们学习 看不懂或者有更好的想法的的请留言^_-
2016-09-24_213732.wmv ...22_排列组合(1).flv 23_排列组合(2).flv 24_概率(1).flv 25_概率(2).flv 26_队列和栈(2).flv 27_大数据(1).flv 28_大数据(2).flv 29_动态规划(1).flv 30_动态规划(2).flv