アルゴリズムnの数は順番にmグループに分けられ、各グループとできるだけ近いです.
7619 ワード
package algorithm;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.TreeMap;
/**
*
* @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 lengthList = new ArrayList();
for(int i=0;i<6;i++){
lengthList.add(new Random().nextInt(100));
}
long startTime=System.currentTimeMillis();
int m = 3;
List> resultList = new ArrayList>();
if (lengthList.size() < m) {
buildResultList(resultList, lengthList);
} else {
int endIndex = lengthList.size() - (m - 2);
int[] tempArr = new int[m - 1];
List combList = new ArrayList();
int num = -1;
// combList
Combine(lengthList, m - 1, tempArr, 0, 0, combList);
int[] resultArr = null;
for (int[] combArr : combList) {
for (int i = 0; i < combArr.length; i++) {
System.out.print(combArr[i] + " ");
}
System.out.println();
int[] sumArr = getSum(combArr, lengthList);
int diffSum = computeDifferent(sumArr);
if (diffSum < num || num == -1) {
num = diffSum;
System.out.println("num=" + num);
resultArr = combArr;
}
}
if (resultArr != null) {
for (int result : resultArr) {
System.out.print(result + " ");
}
}
buildResultList(resultList, lengthList, resultArr);
}
long endTime=System.currentTimeMillis();
long useTime=endTime-startTime;
System.out.print(lengthList.size()+" "+m+" "+useTime+" resultList=" + resultList);
}
// m 。
static void buildResultList(List> resultList,
List dataList) {
for (int i = 0; i < dataList.size(); i++) {
List list = new ArrayList();
list.add(dataList.get(i));
resultList.add(list);
}
}
//
static void buildResultList(List> resultList,
List dataList, int[] resultArr) {
if (resultList == null || dataList == null || resultArr == null) {
return;
}
int j = 0;
int maxJ = 0;
for (int i = 0; i <= resultArr.length; i++) {
if (i == resultArr.length) {
maxJ = dataList.size();
} else {
maxJ = resultArr[i];
}
List list = new ArrayList();
for (; j < maxJ; j++) {
list.add(dataList.get(j));
}
resultList.add(list);
}
}
// 。 0--2 2--5 5--list
static int[] getSum(int[] combArr, List dataList) {
if (combArr == null || dataList == null) {
return null;
}
int[] sumArr = new int[combArr.length + 1];
int j = 0;
int sum = 0;
int maxJ = 0;
for (int i = 0; i <= combArr.length; i++) {
if (i == combArr.length) {
maxJ = dataList.size();
} else {
maxJ = combArr[i];
}
for (; j < maxJ; j++) {
sum += dataList.get(j);
}
sumArr[i] = sum;
System.out.println("sum=" + sum);
sum = 0;
}
return sumArr;
}
// ，
static int computeDifferent(int[] sumArr) {
int diffSum = 0;
for (int i = 0; i < sumArr.length; i++) {
for (int j = i + 1; j < sumArr.length; j++) {
diffSum += Math.abs(sumArr[i] - sumArr[j]);
}
}
System.out.println("diffSum=" + diffSum);
return diffSum;
}
//
private static void Combine(List lengthList, int num,
int[] tempArr, int tempArrIndex, int low, List combList) {
if (lengthList == null || lengthList.size() < num) {
return;
}
if (num == 0) {
if (tempArr[tempArr.length - 1] != lengthList.size()) {
combList.add(tempArr);
}
} else {
for (int i = low; i < lengthList.size(); i++) {
tempArr[tempArrIndex] = i + 1;
Combine(lengthList, num - 1, tempArr, ++tempArrIndex, i + 1,
combList);
int[] newTempArr = new int[tempArr.length];
System.arraycopy(tempArr, 0, newTempArr, 0, tempArr.length - 1);
tempArr = newTempArr;
tempArrIndex--;
}
}
}
}
2、
package algorithm;
import java.util.ArrayList;
import java.util.List;
/**
*
* @Description: ， 。
* ： 、 ， 。 。
* ： 。
* @author thrillerzw
* @version 1.0
* @create time 2014-4-30 9:52:16
*/
public class TestAverage {
public static void main(String[] args) {
List lengthList = new ArrayList();
lengthList.add(1);
lengthList.add(2);
lengthList.add(8);
lengthList.add(6);
lengthList.add(4);
lengthList.add(10);
int m = 3;
List> resultList = new ArrayList>();
if (lengthList.size() < m) {
buildResultList(resultList, lengthList);
} else {
int[] pointArr = findSplitPoint(lengthList, m);
buildResultList(resultList, lengthList, pointArr);
}
System.out.print("resultList=" + resultList);
}
private static int[] findSplitPoint(List lengthList, int m) {
int totalNum = 0;
for (int i = 0; i < lengthList.size(); i++) {
totalNum += lengthList.get(i);
}
//
double average = (double) totalNum / (double) m;
System.out.println("average=" + average);
int groupNum = 0;
int[] pointArr = new int[m - 1];
int pointArrIndex = 0;
double minDiffSum = -1;
int i = 0;
for (; i < lengthList.size(); i++) {
int num = lengthList.get(i);
//
groupNum += num;
double curDiffSum = Math.abs(groupNum - average);
int surplusGroupNum = m - 1 - pointArrIndex;
int surplusDataNum = lengthList.size() - i;
int differNum = surplusDataNum - surplusGroupNum;
if (differNum > 0) {
// <
if (curDiffSum < minDiffSum || minDiffSum == -1) {
minDiffSum = curDiffSum;
} else {
//
pointArr[pointArrIndex] = i;
if (pointArrIndex == m - 2) {
break;
}
pointArrIndex++;
groupNum = num;
minDiffSum = Math.abs(num - average);
}
} else {
// ， 。 。
pointArr[pointArrIndex++] = i;
int point = i + 1;
for (int j = 0; j < surplusGroupNum - 1; j++) {
pointArr[pointArrIndex++] = point++;
}
break;
}
}
return pointArr;
}
static void buildResultList(List> resultList, List dataList) {
for (int i = 0; i < dataList.size(); i++) {
List list = new ArrayList();
list.add(dataList.get(i));
resultList.add(list);
}
}
static void buildResultList(List> resultList, List dataList, int[] resultArr) {
if (resultList == null || dataList == null || resultArr == null) {
return;
}
int j = 0;
int maxJ = 0;
for (int i = 0; i <= resultArr.length; i++) {
if (i == resultArr.length) {
maxJ = dataList.size();
} else {
maxJ = resultArr[i];
}
List list = new ArrayList();
for (; j < maxJ; j++) {
list.add(dataList.get(j));
}
resultList.add(list);
}
}
}