大计算场景下 N个自然数的全排列问题(二)
数据库中
*
* @param pn
* inputData
*/
void printPermutation(ArrayList pn);
void setMax(ArrayList max);
/**
* 得到全排列的具体算法 有递归和非递归等多种算法实现
*
* @param pn
* inputData
*/
boolean nextPermutation(ArrayList pn);
/**
* 全排列API
*
* @param pn
* inputData
*/
void sortInt();
void setPn(ArrayList pn);
}
/**
* 非递归全排列组合算法 并且将该算法平均分割成若干任务，充分利用多核CPU并行运算
*
* @author 蒋彪 版权所有 转载请注明出处
* @param
* @mail nanjingjiangb@hotmail.com
* @data 2013/3/4
*/
class CombinationArgNoRecursion implements CombinationArg {
private ArrayList pn = new ArrayList();
// private ThreadLocal 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