java排列组合算法

import java.util.ArrayList;
import java.util.List;

/**
* 全排列组合算法
* @author mukeliang
* 2009.10.21
*/
public class TestComposite {

public static void main(String[] args) {
// List allList = getFirstData();
// List allList = getSecondData();
List allList = getThirdData();

List targetList = combinatePlan(allList);
System.out.println(targetList);
}

/**
* 进行组合排列
* @param sourceList
* @return List
*/
private static List combinatePlan(List sourceList) {

int[] subSizeArray;
int[] subCountArray;
int sourceCount = sourceList.size(); // 大list的长度
subSizeArray = new int[sourceCount];
subCountArray = new int[sourceCount];// 子list当前的值
int targetCount = 1;
for (int i = 0; i < sourceCount; i++) {
List subList = (List) sourceList.get(i);
int size = subList.size();
subSizeArray[i] = size; // 存放每个子list的长度
targetCount *= size; // 最终要返回的list长度
subCountArray[i] = 0; // 从0开始 每个都是0
// a.println("subCountArray[i]:"+subCountArray[i]);
}

List targetList = new ArrayList(targetCount);
// targetCount
for (int i = 0; i < targetCount; i++) {
// 记录每个结果应该包含的元素个数
List targetSub = new ArrayList(sourceCount);
for (int k = 0; k < sourceCount; k++) {
int subIndex = subCountArray[k];
targetSub.add(((List) sourceList.get(k)).get(subIndex));
}
addCount(subSizeArray, subCountArray);
targetList.add(targetSub);
}

return targetList;

}

/**
* 计算List下标: 总是先数最后一位，最后一位数到最大值以后进一位
* @param subSizeArray
* @param subCountArray
*/
private static void addCount(int[] subSizeArray, int[] subCountArray) {

// subCountArray数组的每个元素都是0 但是个数来记录循环要取的位置
for (int i = subCountArray.length - 1; i >= 0; i--) {
if (subCountArray[i] < subSizeArray[i] - 1) {
subCountArray[i]++;
return;
} else {
subCountArray[i] = 0;
}
}
}

/**
* 组合结果:
* list1下标 list2下标
* 0 0
* 0 1
* 0 2
* 1 0
* 1 1
* 1 2
* 2 0
* 2 1
* 2 2
* @return List
*/
private static List getFirstData(){
List list1 = new ArrayList();
list1.add("王一");
list1.add("王二");
list1.add("王三");

List list2 = new ArrayList();
list2.add("张一");
list2.add("张二");
list2.add("张三");

List allList = new ArrayList();
allList.add(list1);
allList.add(list2);

return allList;
}

/**
* 组合结果:
* list1下标 list2下标 list3下标
* 0 0 0
* 0 0 1
* 0 1 0
* 0 1 1
* 1 0 0
* 1 0 1
* 1 1 0
* 1 1 1
* @return List
*/
private static List getSecondData(){
List list1 = new ArrayList();
list1.add("王一");
list1.add("王二");

List list2 = new ArrayList();
list2.add("张一");
list2.add("张二");

List list3 = new ArrayList();
list3.add("刘一");
list3.add("刘二");

List allList = new ArrayList();
allList.add(list1);
allList.add(list2);
allList.add(list3);

return allList;
}

/**
* 组合结果:
* list1下标 list2下标
* 0 0
* 1 0
* @return List
*/
private static List getThirdData(){
List list1 = new ArrayList();
list1.add("王一");
list1.add("王二");

List list2 = new ArrayList();
list2.add("张一");

List allList = new ArrayList();
allList.add(list1);
allList.add(list2);

return allList;
}

}