求组合算法 本帖最后由 JebySin 于 2011-06-24 23:31:35 编辑 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 想了一下,取组合算法很简单。设有n个元素,组合数量有2的n次方种。对 0 到 2的n次方-1 中的每个数,考察其二进制位形式,位数为1代表相应元素加入到组合,0则不加入该元素至组合。代码如下:import java.util.ArrayList;import java.util.List;public class Combinations { /* 取组合方法 * 参数: list ---- 原始数组 * 返回: 包含所有组合数组的数组 */ public static List<List<Object>> getCombinations(List<Object> list) { List<List<Object>> result = new ArrayList<List<Object>>(); long n = (long)Math.pow(2,list.size()); List<Object> combine; for (long l=0L; l<n; l++) { combine = new ArrayList<Object>(); for (int i=0; i<list.size(); i++) { if ((l>>>i&1) == 1) combine.add(list.get(i)); } result.add(combine); } return result; } //测试 public static void main(String[] args) { ArrayList<Object> list = new ArrayList<Object>(); list.add("a"); list.add("b"); list.add("c"); List<List<Object>> result = getCombinations(list); System.out.println(list.toString()); System.out.println(result.toString()); }} 组合算法,可以采用模拟进制的方式for exampleString[][] s = {{"a","b"}, {"c", "d", "e"}, {"f", "g"}};//求s[0],s[1],s[2]中的元素的所有组合void combie(s) { int[] dig = new int[s.length]; //用来模拟进位 Arrays.fill(dig, 0); while (dig[0] < s[0].length) { //进位最高位不满最大的时候循环 for (int i=0; i<s.length; i++) { System.out.prinf("%s ", s[i][dig[i]]); //打印每个数组的当前进位位置的元素 } System.out.println(); dig[dig.length-1]++; //模拟进位,末位+1 for (int i=dig.length-1; i>0; i--) { if (dig[i] == s[i].length) { //当某进位位置达到最大时往前进位 dig[i] = 0; //当前位清0恢复最小状态 dig[i-1]++; //进位 } else { break; //不满足进位时break } } }} if ((l>>>i&1) == 1) 这一句能否解释下,还没用过。 l>>>i&1l右移i位,再与1进行按位与操作(l>>>i&1) == 1的实际效果为取得l的二进制数的从右往左数第i+1位,判断其是否为1 不知道LZ做的是什么组合?除了4L说的,多个集合里分别取一个元素进行组合外,一般还有一个集合里取n个元素进行组合,一样也可以采用模拟进位的方式,如String s = {"a", "b", "c", "d", "e"};//从s里取出n个元素组合void combine(String[] s, int n) { int[] dig = new int[s.length]; //进位用数组 StringBuilder state = new StringBuilder(); for (int i=s.length-1, j=0; i>=0; i--, j++) { //初始化进位数组状态 if (s.length-i>n) { //如s有5个元素,n为2,即取2个元素组合 dig[i] = 0; //那么初始状态为 00011 } else { dig[i] = 1; } state.append(dig[i]); } String max = state.toString(); //获取进位的最大状态,如上面的假设 11000 String min = state.reverse().toString();//获取进位的最小状态,即数组初始状态 00011 while (max.compareTo(min) >= 0) { //当最小状态比不大于最大状态的时候循环 if (min.length()-min.replaceAll("1", "").length() == n) { //当进位状态中 for (int i=0; i<s.length; i++) { //1的个数为n时打印 if (dig[i] == 1) {System.out.printf("%s ", s[i]);} } System.out.println(); } dig[dig.length-1]++; //模拟进位,末位+1 for (int i=dig.length-1; i>0; i--) { if (dig[i] == 2) { //当某位进位位置达到最大状态时 dig[i] = 0; //清0 dig[i-1]++; //往前进位 } else { break; //不满足进位 break } } min = Arrays.toString(dig).replaceAll("\\D+", ""); //重新获得进位状态 }} 我的理解,既然LZ提到了与排列对应的组合,他指的应当是概率论中排列与组合的基本概念。即从一个给定的集合中取得所有可能的排列或所有的组合。取元素个数为x的组合是给这个问题加一个约束条件,取得的结果是总结果的一个子集。 如果向做全组合,可以通过一个循环调用for exampleString[] s = {"a", "b", "c", "d", "e"};for (int i=1; i<=s.length; i++) { combine(s, i); //}也就是说从集合s里,取1个元素组合,然后再取2个元素组合,然后再3个元素组合,等等,直到n个元素组合,这个n=s的总个数为止就可以了。 线程问题,线程已经取消了,也返回取消成功了,却还在继续运行,求救啊..:) Java中,如何获得网关的地址 大家是怎么做hibernate级联删除的 有对ClassLoader熟悉的朋友没?请教一个问题 我用的是jdk1.5怎么打印不出来中文啊,大家看看下面的程序 问一个美国cs研究生作业 关于顶级嵌套类的问题 如何将一个文件中的内容加入到一个数组中? jbuilder8中配置jdbc连接问题 请教jbuild5中如何加载任何可执行文件? java初学关于反射问题 JAVA界面实在让我无语了
设有n个元素,组合数量有2的n次方种。
对 0 到 2的n次方-1 中的每个数,考察其二进制位形式,位数为1代表相应元素加入到组合,0则不加入该元素至组合。
代码如下:
import java.util.ArrayList;
import java.util.List;public class Combinations { /* 取组合方法
* 参数: list ---- 原始数组
* 返回: 包含所有组合数组的数组
*/
public static List<List<Object>> getCombinations(List<Object> list) {
List<List<Object>> result = new ArrayList<List<Object>>();
long n = (long)Math.pow(2,list.size());
List<Object> combine;
for (long l=0L; l<n; l++) {
combine = new ArrayList<Object>();
for (int i=0; i<list.size(); i++) {
if ((l>>>i&1) == 1)
combine.add(list.get(i));
}
result.add(combine);
}
return result;
}
//测试
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
list.add("a");
list.add("b");
list.add("c");
List<List<Object>> result = getCombinations(list);
System.out.println(list.toString());
System.out.println(result.toString());
}}
for exampleString[][] s = {{"a","b"}, {"c", "d", "e"}, {"f", "g"}};
//求s[0],s[1],s[2]中的元素的所有组合void combie(s) {
int[] dig = new int[s.length]; //用来模拟进位
Arrays.fill(dig, 0); while (dig[0] < s[0].length) { //进位最高位不满最大的时候循环
for (int i=0; i<s.length; i++) {
System.out.prinf("%s ", s[i][dig[i]]); //打印每个数组的当前进位位置的元素
}
System.out.println(); dig[dig.length-1]++; //模拟进位,末位+1
for (int i=dig.length-1; i>0; i--) {
if (dig[i] == s[i].length) { //当某进位位置达到最大时往前进位
dig[i] = 0; //当前位清0恢复最小状态
dig[i-1]++; //进位
} else {
break; //不满足进位时break
}
}
}
}
if ((l>>>i&1) == 1) 这一句能否解释下,还没用过。
l右移i位,再与1进行按位与操作(l>>>i&1) == 1的实际效果为取得l的二进制数的从右往左数第i+1位,判断其是否为1
除了4L说的,多个集合里分别取一个元素进行组合外,一般还有一个集合里取n个元素进行组合,一样也可以采用模拟进位的方式,如String s = {"a", "b", "c", "d", "e"};
//从s里取出n个元素组合void combine(String[] s, int n) {
int[] dig = new int[s.length]; //进位用数组
StringBuilder state = new StringBuilder();
for (int i=s.length-1, j=0; i>=0; i--, j++) { //初始化进位数组状态
if (s.length-i>n) { //如s有5个元素,n为2,即取2个元素组合
dig[i] = 0; //那么初始状态为 00011
}
else {
dig[i] = 1;
}
state.append(dig[i]);
}
String max = state.toString(); //获取进位的最大状态,如上面的假设 11000
String min = state.reverse().toString();//获取进位的最小状态,即数组初始状态 00011
while (max.compareTo(min) >= 0) { //当最小状态比不大于最大状态的时候循环
if (min.length()-min.replaceAll("1", "").length() == n) { //当进位状态中
for (int i=0; i<s.length; i++) { //1的个数为n时打印
if (dig[i] == 1) {System.out.printf("%s ", s[i]);}
}
System.out.println();
} dig[dig.length-1]++; //模拟进位,末位+1
for (int i=dig.length-1; i>0; i--) {
if (dig[i] == 2) { //当某位进位位置达到最大状态时
dig[i] = 0; //清0
dig[i-1]++; //往前进位
} else {
break; //不满足进位 break
}
}
min = Arrays.toString(dig).replaceAll("\\D+", ""); //重新获得进位状态
}
}
for example
String[] s = {"a", "b", "c", "d", "e"};
for (int i=1; i<=s.length; i++) {
combine(s, i); //
}
也就是说从集合s里,取1个元素组合,然后再取2个元素组合,然后再3个元素组合,等等,直到n个元素组合,这个n=s的总个数为止就可以了。