以前还整理过一个js的，下次读到了可以写过来。
求多个数组之间元素的排列组合问题，方法有两个：递归法、循环法。
首先应该认识到的是：
所有可以用递归实现的操作都可以转化为用while、for等循环实现。
递归法
优缺点：
数组数量不太多时用递归法确实使程序比较简洁，数组数量太多时递归函数栈过大，有可能导致运行时栈溢出。而且相对常用的算法如普通循环等，运行效率较低。
实现代码一
/**
* 写法一，递归计算所有组合
* @param inputList 所有数组的列表
* */
public List<String> combination(List<String> inputList){
List<String> resList = new ArrayList<>();
combinationInt(inputList, resList, 0,
new char[inputList.size()]);
return resList;
}
private void combinationInt(List<String> inputList, List<String> resList,
int ind, char[] arr) {
if(ind == inputList.size()){
resList.add(new String(arr));
return;
}
for(char c: inputList.get(ind).toCharArray()){
arr[ind] = c;
combinationInt(inputList, resList, ind + 1, arr);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
测试程序
//测试部分
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("ab");
list.add("12");
list.add("AB");
List<String> result=combination(list);
System.out.println("组合结果：");
for (String string : result) {
System.out.println(string);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
实现代码二
/**
* 写法二，递归计算所有组合
* @param inputList 所有数组的列表，数组用List<Integer>存储
* @param beginIndex 代表每一个数组的在inputList中的索引
* @param arr 用于保存每一次递归生成的组合
* */
public void calculateCombination(List<List<Integer>> inputList, int beginIndex, int[] arr) {
if(beginIndex == inputList.size()){
//在这里进行你自己的处理，比如打印组合的结果
for (int i : arr) {
System.out.print(i+", ");
}
System.out.println();
return;
}
for(int c: inputList.get(beginIndex)){
arr[beginIndex] = c;
calculateCombination(inputList, beginIndex + 1, arr);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
测试程序
//测试部分
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<>();
list1.add(0);
list1.add(1);
list1.add(2);
List<Integer> list2 = new ArrayList<>();
list2.add(3);
list2.add(4);
list2.add(5);
List<Integer> list3 = new ArrayList<>();
list3.add(6);
list3.add(7);
list3.add(8);
List<List<Integer>> allList = new ArrayList<>();
allList.add(list1);
allList.add(list2);
allList.add(list3);
calculateCombination(allList, 0, new int[allList.size()]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
循环法
优缺点：
采用循环方式程序编写较递归法略复杂，但是执行效率高，不管数组数量多少，都不会发生栈溢出。
代码
/**
* 算法二，非递归计算所有组合
* @param inputList 所有数组的列表
* */
public void calculateCombination(List<List<Integer>> inputList) {
List<Integer> combination = new ArrayList<Integer>();
int n=inputList.size();
for (int i = 0; i < n; i++) {
combination.add(0);
}
int i=0;
boolean isContinue=false;
do{
//打印一次循环生成的组合
for (int j = 0; j < n; j++) {
System.out.print(inputList.get(j).get(combination.get(j))+", ");
}
System.out.println();
i++;
combination.set(n-1, i);
for (int j = n-1; j >= 0; j--) {
if (combination.get(j)>=inputList.get(j).size()) {
combination.set(j, 0);
i=0;
if (j-1>=0) {
combination.set(j-1, combination.get(j-1)+1);
}
}
}
isContinue=false;
for (Integer integer : combination) {
if (integer != 0) {
isContinue=true;
}
}
}while (isContinue);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
测试程序
//测试部分
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<>();
list1.add(0);
list1.add(1);
list1.add(2);
List<Integer> list2 = new ArrayList<>();
list2.add(3);
list2.add(4);
list2.add(5);
List<Integer> list3 = new ArrayList<>();
list3.add(6);
list3.add(7);
list3.add(8);
List<List<Integer>> allList = new ArrayList<>();
allList.add(list1);
allList.add(list2);
allList.add(list3);
calculateCombination(allList);
}