做组合算法，参数可能为42个或者72个，现有东东做C(42,4) C(72,4)都可以，但是要求最多要做到C(42,11) C(72,11)
这个时候运算的就很慢了，而且算到最后JVM分配的内存都不够。
望高手提供下解决方案，算法是朋友给的，稍微改了下。谢谢
以下是已有的代码：import java.util.ArrayList;
import java.util.BitSet;
import java.util.Date;public class Combination {
private ArrayList<String> combList = new ArrayList<String>(); public void mn(String[] array, int n) {
int m = array.length;
// 创建一个位 set,并设置其大小为m
BitSet bs = new BitSet(m);
// 默认情况下，set 中所有位的初始值都是false,这里循环将其默认值都修改为true,只修改前n位
for (int i = 0; i < n; i++) {
bs.set(i, true);
}
do {
printAll(array, bs);
} while (moveNext(bs, m));
} /**
* 输出生成的组合结果
*
* @param array 数组
* @param bs 数组元素是否显示的标志位集合
*/
private void printAll(String[] array, BitSet bs) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < array.length; i++) {
// 在mn方法操作中，只将前n位的值修改为true，所以这里只有前n位通过if判断,这里在bitSet中存的是数组的下标
if (bs.get(i)) {
sb.append(array[i]).append(',');
}
}
//设置length属性，去掉最后多加的一个','
sb.setLength(sb.length() - 1);
combList.add(sb.toString());
} /**
* 1、start 第一个true片段的起始位，end截止位 2、把第一个true片段都置false
* 3、数组从0下标起始到以第一个true片段元素数量减一为下标的位置都置true 4、把第一个true片段end截止位置true
*
* @param bs 数组是否显示的标志位
* @param m 数组长度
* @return boolean 是否还有其他组合
*/
private boolean moveNext(BitSet bs, int m) {
int start = -1;
// 该操作是获得第一个为true的bitset的下标,其值给start
while (start < m) {
// 先++是因为初始给的值为-1
if (bs.get(++start)) {
break;
}
}
// 如果bitset中没有一个true那么完成while后start已经达最大,直接返回false
if (start >= m) {
return false;
}
// 从第一个为true的位置作为开始和结束位置
int end = start;
// 依次走，找到第一个为false的位置下标,其值给end
while (end < m) {
if (!bs.get(++end)) {
break;
}
}
// 如果走到最后都没有找到false,直接返回false
if (end >= m) {
return false;
}
for (int i = start; i < end; i++) {
bs.set(i, false);
}
for (int i = 0; i < end - start - 1; i++) {
// BitSet的set()方法：:将指定索引处的位设置为 true
bs.set(i);
}
bs.set(end);
return true;
} public static void main(String[] args) throws Exception {
Combination comb = new Combination();
Date begin=new Date();
//20Q的42个参数
//String[] strArr=new String[] { "1", "0", "2", "8", "4", "17", "2", "7", "8", "5", "3", "1", "0", "1", "1", "1", "1", "49", "2", "9", "13", "1", "0", "0", "7", "0", "7", "7", "7", "2", "29", "0", "9", "11", "5", "2", "19", "0", "9", "10", "7", "0"};
//72个参数的时候
String[] strArr=new String[] { "1", "0", "2", "8", "4", "17", "2", "7", "8", "5", "3", "1", "0", "1", "1", "1", "1", "49", "2", "9", "13", "1", "0", "0", "7", "0", "7", "7", "7", "2", "29", "0", "9", "11", "5", "2", "19", "0", "9", "10", "7", "0","1", "0", "2", "8", "4", "17", "2", "7", "8", "5", "3", "1", "0", "1", "1", "1", "1", "49", "2", "9", "13", "1", "0", "0", "7", "0", "7", "7", "7", "2"};
//设置为4，表示做的是取4个数来排列
comb.mn(strArr, 4); // 输出计算后的排列结果
// for (int i = 0; i < comb.getCombList().size(); i++) {
// System.out.println(comb.getCombList().get(i));
// }
Date end=new Date();
long time=end.getTime()-begin.getTime();
System.out.println("运算总时间为:"+time/1000+"秒"+time%1000);
System.out.println("得到的排列的总数量为："+comb.getCombList().size());
} public ArrayList<String> getCombList() {
return combList;
}
}
这个时候运算的就很慢了，而且算到最后JVM分配的内存都不够。
望高手提供下解决方案，算法是朋友给的，稍微改了下。谢谢
以下是已有的代码：import java.util.ArrayList;
import java.util.BitSet;
import java.util.Date;public class Combination {
private ArrayList<String> combList = new ArrayList<String>(); public void mn(String[] array, int n) {
int m = array.length;
// 创建一个位 set,并设置其大小为m
BitSet bs = new BitSet(m);
// 默认情况下，set 中所有位的初始值都是false,这里循环将其默认值都修改为true,只修改前n位
for (int i = 0; i < n; i++) {
bs.set(i, true);
}
do {
printAll(array, bs);
} while (moveNext(bs, m));
} /**
* 输出生成的组合结果
*
* @param array 数组
* @param bs 数组元素是否显示的标志位集合
*/
private void printAll(String[] array, BitSet bs) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < array.length; i++) {
// 在mn方法操作中，只将前n位的值修改为true，所以这里只有前n位通过if判断,这里在bitSet中存的是数组的下标
if (bs.get(i)) {
sb.append(array[i]).append(',');
}
}
//设置length属性，去掉最后多加的一个','
sb.setLength(sb.length() - 1);
combList.add(sb.toString());
} /**
* 1、start 第一个true片段的起始位，end截止位 2、把第一个true片段都置false
* 3、数组从0下标起始到以第一个true片段元素数量减一为下标的位置都置true 4、把第一个true片段end截止位置true
*
* @param bs 数组是否显示的标志位
* @param m 数组长度
* @return boolean 是否还有其他组合
*/
private boolean moveNext(BitSet bs, int m) {
int start = -1;
// 该操作是获得第一个为true的bitset的下标,其值给start
while (start < m) {
// 先++是因为初始给的值为-1
if (bs.get(++start)) {
break;
}
}
// 如果bitset中没有一个true那么完成while后start已经达最大,直接返回false
if (start >= m) {
return false;
}
// 从第一个为true的位置作为开始和结束位置
int end = start;
// 依次走，找到第一个为false的位置下标,其值给end
while (end < m) {
if (!bs.get(++end)) {
break;
}
}
// 如果走到最后都没有找到false,直接返回false
if (end >= m) {
return false;
}
for (int i = start; i < end; i++) {
bs.set(i, false);
}
for (int i = 0; i < end - start - 1; i++) {
// BitSet的set()方法：:将指定索引处的位设置为 true
bs.set(i);
}
bs.set(end);
return true;
} public static void main(String[] args) throws Exception {
Combination comb = new Combination();
Date begin=new Date();
//20Q的42个参数
//String[] strArr=new String[] { "1", "0", "2", "8", "4", "17", "2", "7", "8", "5", "3", "1", "0", "1", "1", "1", "1", "49", "2", "9", "13", "1", "0", "0", "7", "0", "7", "7", "7", "2", "29", "0", "9", "11", "5", "2", "19", "0", "9", "10", "7", "0"};
//72个参数的时候
String[] strArr=new String[] { "1", "0", "2", "8", "4", "17", "2", "7", "8", "5", "3", "1", "0", "1", "1", "1", "1", "49", "2", "9", "13", "1", "0", "0", "7", "0", "7", "7", "7", "2", "29", "0", "9", "11", "5", "2", "19", "0", "9", "10", "7", "0","1", "0", "2", "8", "4", "17", "2", "7", "8", "5", "3", "1", "0", "1", "1", "1", "1", "49", "2", "9", "13", "1", "0", "0", "7", "0", "7", "7", "7", "2"};
//设置为4，表示做的是取4个数来排列
comb.mn(strArr, 4); // 输出计算后的排列结果
// for (int i = 0; i < comb.getCombList().size(); i++) {
// System.out.println(comb.getCombList().get(i));
// }
Date end=new Date();
long time=end.getTime()-begin.getTime();
System.out.println("运算总时间为:"+time/1000+"秒"+time%1000);
System.out.println("得到的排列的总数量为："+comb.getCombList().size());
} public ArrayList<String> getCombList() {
return combList;
}
}
以取三个数为例，
阶段一：
初始一个BitSet，该集合的存参数的数组长度相同，下标对应，
阶段二：
将前三位设置为true,其他的都为false
阶段三：
取得BitSet中值为true的下标值到数组中取得对应的值
阶段四：
修改BitSet中为true值的下标位置。大致就是这个了，方法是别人给的，只是稍微动了下
就是取多的时候就问题了，
java.lang.OutOfMemoryError: Java heap space
直接内存不够，这个运算量是大，但是电脑就受不了了，那那些数学软件的进行的运算就更多了。
诶，求解决方案啊....如果有好的方法思路也行，只要能出结果就好
// for (int i = 0; i < comb.getCombList().size(); i++) {
// System.out.println(comb.getCombList().get(i));
// }
这段代码取消注释可以看到匹配后的结果的，是正确的
绝对要outofmemory
arraylist放int型的话100万以上估计就要挂
不清楚具体数值啊
你不如先把结果存入到数据库或临时文件中再分析
这样至少不会引起outofmemory
bitset 在这里没什么好处，我觉得用个数组做堆栈蛮好，
数组大小为要取几个数，上面就是4,或11，
数组 int stack[4]; int top = 0; top表示栈顶
每个int表示所取的数的下标，而后回朔遍历数据参数array.
压栈出栈的操作我就不说了获取组合的话，可以做一个函数用于获取部分组合结果：
get_comb(String[] array, int start, int count);这个可以使得结果分步处理，解决内存问题。接下来就是根据start恢复遍历堆栈，比如获取第56个数时的堆栈应该是则么样的
这个问题就是计算排列组合的问题了
如下-Xms32m -Xmx800m同时combList.ensureCapacity(1000000);//预先设置list的大小
也可以提高一些速度。
C(42,11)也有42亿的项目，如果按照这个数据量的话，您有什么解决方案不？
我想C(72,11)完成不了，我把C(42,3)到C(42,11)完成了，也算有个交代