package algorithm;
import ;
import ;
import ;
import ;
import ;
import ;
import ;
import ;
/**
*
* @Description: n个数按顺序分成m组，每组和尽量相近
* 思路：先递归求出所有切分点的组合方式，然后分别计算每组中的和,对每组和两两差值的绝对值累加，最小的为最优切分点。
* 如:{1,2,3,4}分2组 可以{1}和{2,3,4} {1,2}和{3,4} {1,2,3}和{4} 不能为{1,3}{2,4}
* 缺点：当list很大，分的组很多的时候，效率很低，几十分钟才能算出来。
* @author thrillerzw
* @version 1.0
* @create time 2014-4-28 下午6:47:19
*/
public class TestCombination {
public static void main(String[] args) {
List<Integer> lengthList = new ArrayList<Integer>();
for(int i=0;i<6;i++){
(new Random().nextInt(100));
}
long startTime=();
int m = 3;
List<List<Integer>> resultList = new ArrayList<List<Integer>>();
if (() < m) {
buildResultList(resultList, lengthList);
} else {
int endIndex = () - (m - 2);
int[] tempArr = new int[m - 1];
List<int[]> combList = new ArrayList<int[]>();
int num = -1;
//所有切分点的组合存入combList
Combine(lengthList, m - 1, tempArr, 0, 0, combList);
int[] resultArr = null;
for (int[] combArr : combList) {
for (int i = 0; i < ; i++) {
(combArr[i] + " ");
}
();
int[] sumArr = getSum(combArr, lengthList);
int diffSum = computeDifferent(sumArr);
if (diffSum < num || num == -1) {
num = diffSum;
("num=" + num);
resultArr = combArr;
}
}
if (resultArr != null) {
for (int result : resultArr) {
(result + " ");
}
}
buildResultList(resultList, lengthList, resultArr);
}
long endTime=();
long useTime=endTime-startTime;
(()+"个数分为"+m+"组使用毫秒时间"+useTime+" resultList=" + resultList);
}
//如果分组数m大于等于集合的长度。
static void buildResultList(List<List<Integer>> resultList,
List<Integer> dataList) {
for (int i = 0; i < (); i++) {
List<Integer> list = new ArrayList<Integer>();
((i));
(list);
}
}
// 根据最优切分点构建结果集
static void buildResultList(List<List<Integer>> resultList,
List<Integer> dataList, int[] resultArr) {
if (resultList == null || dataList == null || resultArr == null) {
return;
}
int j = 0;
int maxJ = 0;
for (int i = 0; i <= ; i++) {
if (i == ) {
maxJ = ();
} else {
maxJ = resultArr[i];
}
List<Integer> list = new ArrayList<Integer>();
for (; j < maxJ; j++) {
((j));
}
(list);
}
}
//每种组合不同段的和。比如0--2 2--5 5--list的结尾
static int[] getSum(int[] combArr, List<Integer> dataList) {
if (combArr == null || dataList == null) {
return null;
}
int[] sumArr = new int[ + 1];
int j = 0;
int sum = 0;
int maxJ = 0;
for (int i = 0; i <= ; i++) {
if (i == ) {
maxJ = ();
} else {
maxJ = combArr[i];
}
for (; j < maxJ; j++) {
sum += (j);
}
sumArr[i] = sum;
("sum=" + sum);
sum = 0;
}
return sumArr;
}
// 数组中值两两比较，差的绝对值的和累加
static int computeDifferent(int[] sumArr) {
int diffSum = 0;
for (int i = 0; i < ; i++) {
for (int j = i + 1; j < ; j++) {
diffSum += (sumArr[i] - sumArr[j]);
}
}
("diffSum=" + diffSum);
return diffSum;
}
// 所有切分点组合
private static void Combine(List<Integer> lengthList, int num,
int[] tempArr, int tempArrIndex, int low, List<int[]> combList) {
if (lengthList == null || () < num) {
return;
}
if (num == 0) {
if (tempArr[ - 1] != ()) {
(tempArr);
}
} else {
for (int i = low; i < (); i++) {
tempArr[tempArrIndex] = i + 1;
Combine(lengthList, num - 1, tempArr, ++tempArrIndex, i + 1,
combList);
int[] newTempArr = new int[];
(tempArr, 0, newTempArr, 0, - 1);
tempArr = newTempArr;
tempArrIndex--;
}
}
}
}