题目看起来很简单，但是要关注两个问题：
1. 避免使用递归算法，因为这样会使计算复杂度成指数级别上升
2. 巨大的计算量下，如何把计算工作切分成若干模块，并行。 现代计算机的特点是多核心，家用PC双核，四核，server上18路，36路核心。把大数据运算切分到各个核心上会事半功倍。
因此我花了周六写了一个代码， 用非递归算法求全排列， 用特定的算法的把计算量分割成若干单元，用java线程池运算。 运算结果写本地文件。
我的本地机器 2.93HZ双核CPU， 4G内存， win7系统，最高作了16个自然数的全排列，进行了一共4亿六千万次的运算，2分钟内完成。这个成绩还是可以的。
更进一步，如果还想提高运算能力， 我会考虑用x86集群， 每个机器上启动一个JVM， 各个JVM之间tcp通信协同作业， 能将运算速度再提高一个数量级。
有兴趣研究更深入算法或者技术实现的可以联系我，以下是我的代码：
[java]
import java.io.FileWriter;
import java.io.IOException;
import java.math.BigInteger;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Date;
import ncurrent.Callable;
import ncurrent.ExecutorService;
import ncurrent.Executors;
import ncurrent.Future;
/**
* 非递归算法 + 分割成若干计算单位并发运算
* 在高计算量下会有明显优势，但是在计算量较小，线程切换会有开销
* 本地机器 2.93HZ双核CPU， 4G内存， win7系统， 16个数的全排列，一共4亿7千万次运算，2分钟内完成
* 如果更进一步，可以考虑用x86机器做集群运算，每个机器上启动一个JVM， JVM之间用tcp通信协调，一起跑
* 有兴趣想深入研究可以联系我
*
* @param <E>
* @param <T>
* @mail nanji
* @data 2013/3/4
*/
public class CombinationTest<E> {
// 计算模块的线程执行框架，线程数保持在CPU核数 + 1， 可以最大榨取机器性能
// private final static ExecutorService exec = Executors
// .newFixedThreadPool(1);
private final static ExecutorService exec = Executors.newCachedThreadPool();
public static void main(String[] args) {
if (args.length < 1) {
return;
}
// 先将这串数字正排序，预先处理
Arrays.sort(args);
ArrayList<Integer> min = Util.changeStringsToArray(args);
Arrays.sort(args, Collections.reverseOrder());
ArrayList<Integer> max = Util.changeStringsToArray(args);
ArrayList diffBlock = getStepData(min, max);
for (int k = 0; k < diffBlock.size() - 1; k++) {
CombinationArg task = new CombinationArgNoRecursion();
task.setPn((ArrayList<Integer>) diffBlock.get(k));
task.setMax((ArrayList<Integer>) diffBlock.get(k + 1));
Future future = exec.submit(task);
// future.get();
}
// exec.shutdown();
}
/**
* 分割待排序数据，分割成若干个起点的小块计算量 算法待优化，可考虑CPU，内存等限制计算快的大小
*
* @param pn
* @return
*/
public static ArrayList getStepData(ArrayList<Integer> min,
ArrayList<Integer> max) {
ArrayList result = new ArrayList();
// 循环把第二位和第一位交换
// 比如，原始数据是1,2,3 ,4, 5
// 那么可以分割成 12345 ~ 21345 ~ 31245~ 41235~ 51234 几个近似区间来计算
result.add((ArrayList) min.clone());
for (int j = 1; j < max.size(); j++) {
Collections.swap(min, j, 0);
result.add((ArrayList) min.clone());
}
result.add(max);
return result;
}
}
/**
* 全排列组合算法接口 继承自Callable，方便在多线程环境下扩展
*
* @param <E>
* @param <T>
* @mail nanji
* @data 2013/3/4
*/
interface CombinationArg<E, T> extends Callable<T> {
/**
* 输出全排列的方法 在多JVM并行环境考虑打印到分散式文档，或者内存数据库中
*
* @param pn
* inputData
*/
void printPermutation(ArrayList<E> pn);
void setMax(ArrayList max);
/**
* 得到全排列的具体算法 有递归和非递归等多种算法实现
*
* @param pn
* inputData
*/
boolean nextPermutation(ArrayList<E> pn);
/**
* 全排列API
*
* @param pn
* inputData
*/
void sortInt();
void setPn(ArrayList pn);
}
/**
* 非递归全排列组合算法 并且将该算法平均分割成若干任务，充分利用多核CPU并行运算
*
* @param <E>
* @mail nanji
* @data 2013/3/4
*/
class CombinationArgNoRecursion<E> implements CombinationArg {
private ArrayList pn = new ArrayList();
// private ThreadLocal<WriteLog> write = new ThreadLocal();
private WriteLog write = new WriteLogToFile();
private SimpleDateFormat formatter = new SimpleDateFormat(
"dd-MMM-yyyy HH:mm:ss:SSS");
private BigInteger max = new BigInteger("0");
@Override
public void setPn(ArrayList pn) {
this.pn = pn;
}
@Override
public void setMax(ArrayList max) {
this.max = Util.changeArrayListToBigInteger(max);
}
public CombinationArgNoRecursion() {
}
@Override
public Object call() throws Exception {
sortInt();
return true;
}
private int firstFlg = 0;
/**
* 全排列数字
*
* @param num
*/
public void sortInt() {
System.out.println("/*****" + Thread.currentThread().getName()
+ " 开始求全排列 ...... "
+ formatter.format(new Date(System.currentTimeMillis()))
+ "*******/");
System.out.println("/*****************" + "start num is: "
+ Util.changeArrayListToBigInteger(pn) + " end num is: " + max
+ "***********************/");
write.setWriter(Thread.currentThread().getName() + "打印全排序.txt");
while (nextPermutation(pn)) {
}
write.closeWrite();
System.out.println("/*****" + Thread.currentThread().getName()
+ " 结束求全排列 ...... "
+ formatter.format(new Date(System.currentTimeMillis()))
+ "*******/");
}
/**
* 在屏幕上打印出全排列
*
* @param str
*/
@Override
public void printPermutation(ArrayList pn) {
write.printPermutation(pn);
}
/**
*
* 根据当前的排列p，计算下一个排列。
*
* 原则是从1234–>4321，若p已经是最后一个排列，传回false，否则传回true。
*
* @param pn
* 计算起点
* @param max
* 计算终点
*/
@Override
public boolean nextPermutation(ArrayList pn) {
if (firstFlg == 0) {
printPermutation(pn);
firstFlg++;
}
int last = pn.size() - 1;
int i, j, k;
// 从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。
i = last;
while (i > 0 && ((Integer) pn.get(i) < (Integer) pn.get(i - 1)))
i--;
// 若没有后面的数大于前面的数的情况，说明已经到了最后一个排列，返回false。
if (i == 0)
return false;
// 从后查到i，查找大于p[i - 1]的最小的数，记入k
k = i;
for (j = last; j >= i; j--)
if (((Integer) pn.get(j) > (Integer) pn.get(i - 1))
&& ((Integer) pn.get(j) < (Integer) pn.get(k)))
k = j;
// 交换p[k]和p[i - 1]
Collections.swap(pn, k, i - 1);
// 倒置p[last]到p[i]
for (j = last, k = i; j > k; j--, k++)
Collections.swap(pn, j, k);
printPermutation(pn);
// 如果超出限制，则停止计算
BigInteger now = Util.changeArrayListToBigInteger(pn);
if (pareTo(max) > 0) {
return false;
}
return true;
}
}
interface WriteLog {
void writeLog(String log);
void printPermutation(ArrayList pn);
void setWriter(String fileName);
void closeWrite();
}
class WriteLogToFile implements WriteLog {
ThreadLocal<FileWriter> writer = new ThreadLocal();
public void setWriter(String fileName) {
try {
writer.set(new FileWriter(fileName, true));
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void closeWrite() {
try {
writer.get().close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* B方法追加文件：使用FileWriter
*
* @param fileName
* @param content
*/
public void appendMethod(String content) {
try {
// 打开一个写文件器，构造函数中的第二个参数true表示以追加形式写文件
writer.get().write(content);
// 避免频繁的openWrite, closeWrite，增加CPU负担
// writer.close();
} catch (IOException e) {
e.printStackTrace();
}
}
@Override
public void writeLog(String log) {
appendMethod(log);
appendMethod("\r\n");
}
@Override
public void printPermutation(ArrayList pn) {
StringBuffer tmp = new StringBuffer();
for (int i = 0; i < pn.size(); i++) {
tmp.append(pn.get(i)).append(",");
}
writeLog(tmp.toString());
}
}
class Util {
public static ArrayList<Integer> changeStringsToArray(String[] s) {
ArrayList<Integer> px = new ArrayList<Integer>(s.length);
for (String x : s) {
px.add(Integer.parseInt(x));
}
return px;
}
public static BigInteger changeArrayListToBigInteger(ArrayList<Integer> pn) {
StringBuffer orgData = new StringBuffer();
for (int j = 0; j < pn.size(); j++) {
orgData.append(pn.get(j));
}
return new BigInteger(orgData.toString());
}
public static ArrayList<Integer> changeBigIntegerToArrL(BigInteger tmp) {
String x = tmp.toString();
ArrayList<Integer> r = new ArrayList<Integer>();
for (int j = 0; j < x.length(); j++) {
r.add(Integer.parseInt(String.valueOf(x.charAt(j))));
}
return r;
}
}
联系客服
