本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积。分享给大家供大家参考，具体如下：
什么是笛卡尔积？
在数学中，两个集合X和Y的笛卡儿积（Cartesian product），又称直积，表示为X × Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。
假设集合A={a,b}，集合B={0,1,2}，则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}。
如何用程序算法实现笛卡尔积？
如果编程前已知集合的数量，通过程序的多次循环即可得出笛卡尔积。但是如果编程前不知道集合的数量，如何得到笛卡尔积哪？比如集合表示List < List<String>> list；这个list在编程前list的数量是未知的。下面的代码使用递归和循环两种方法实现未知维度集合的笛卡尔积：
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * 循环和递归两种方式实现未知维度集合的笛卡尔积 * Created on 2015-05-22 * @author luweijie */public class Descartes { /** * 递归实现dimValue中的笛卡尔积，结果放在result中 * @param dimValue 原始数据 * @param result 结果数据 * @param layer dimValue的层数 * @param curList 每次笛卡尔积的结果 */ private static void recursive (List<List<String>> dimValue, List<List<String>> result, int layer, List<String> curList) { if (layer < dimValue.size() - 1) { if (dimValue.get(layer).size() == 0) { recursive(dimValue, result, layer + 1, curList); } else { for (int i = 0; i < dimValue.get(layer).size(); i++) { List<String> list = new ArrayList<String>(curList); list.add(dimValue.get(layer).get(i)); recursive(dimValue, result, layer + 1, list); } } } else if (layer == dimValue.size() - 1) { if (dimValue.get(layer).size() == 0) { result.add(curList); } else { for (int i = 0; i < dimValue.get(layer).size(); i++) { List<String> list = new ArrayList<String>(curList); list.add(dimValue.get(layer).get(i)); result.add(list); } } } } /** * 循环实现dimValue中的笛卡尔积，结果放在result中 * @param dimValue 原始数据 * @param result 结果数据 */ private static void circulate (List<List<String>> dimValue, List<List<String>> result) { int total = 1; for (List<String> list : dimValue) { total *= list.size(); } String[] myResult = new String[total]; int itemLoopNum = 1; int loopPerItem = 1; int now = 1; for (List<String> list : dimValue) { now *= list.size(); int index = 0; int currentSize = list.size(); itemLoopNum = total / now; loopPerItem = total / (itemLoopNum * currentSize); int myIndex = 0; for (String string : list) { for (int i = 0; i < loopPerItem; i++) { if (myIndex == list.size()) { myIndex = 0; } for (int j = 0; j < itemLoopNum; j++) { myResult[index] = (myResult[index] == null? "" : myResult[index] + ",") + list.get(myIndex); index++; } myIndex++; } } } List<String> stringResult = Arrays.asList(myResult); for (String string : stringResult) { String[] stringArray = string.split(","); result.add(Arrays.asList(stringArray)); } } /** * 程序入口 * @param args */ public static void main (String[] args) { List<String> list1 = new ArrayList<String>(); list1.add("1"); list1.add("2"); List<String> list2 = new ArrayList<String>(); list2.add("a"); list2.add("b"); List<String> list3 = new ArrayList<String>(); list3.add("3"); list3.add("4"); list3.add("5"); List<String> list4 = new ArrayList<String>(); list4.add("c"); list4.add("d"); list4.add("e"); List<List<String>> dimValue = new ArrayList<List<String>>(); dimValue.add(list1); dimValue.add(list2); dimValue.add(list3); dimValue.add(list4); List<List<String>> recursiveResult = new ArrayList<List<String>>(); // 递归实现笛卡尔积 recursive(dimValue, recursiveResult, 0, new ArrayList<String>()); System.out.println("递归实现笛卡尔乘积: 共 " + recursiveResult.size() + " 个结果"); for (List<String> list : recursiveResult) { for (String string : list) { System.out.print(string + " "); } System.out.println(); } List<List<String>> circulateResult = new ArrayList<List<String>>(); circulate(dimValue, circulateResult); System.out.println("循环实现笛卡尔乘积: 共 " + circulateResult.size() + " 个结果"); for (List<String> list : circulateResult) { for (String string : list) { System.out.print(string + " "); } System.out.println(); } }} |
输出结果是：
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
递归实现笛卡尔乘积: 共 36 个结果1 a 3 c1 a 3 d1 a 3 e1 a 4 c1 a 4 d1 a 4 e1 a 5 c1 a 5 d1 a 5 e1 b 3 c1 b 3 d1 b 3 e1 b 4 c1 b 4 d1 b 4 e1 b 5 c1 b 5 d1 b 5 e2 a 3 c2 a 3 d2 a 3 e2 a 4 c2 a 4 d2 a 4 e2 a 5 c2 a 5 d2 a 5 e2 b 3 c2 b 3 d2 b 3 e2 b 4 c2 b 4 d2 b 4 e2 b 5 c2 b 5 d2 b 5 e循环实现笛卡尔乘积: 共 36 个结果1 a 3 c1 a 3 d1 a 3 e1 a 4 c1 a 4 d1 a 4 e1 a 5 c1 a 5 d1 a 5 e1 b 3 c1 b 3 d1 b 3 e1 b 4 c1 b 4 d1 b 4 e1 b 5 c1 b 5 d1 b 5 e2 a 3 c2 a 3 d2 a 3 e2 a 4 c2 a 4 d2 a 4 e2 a 5 c2 a 5 d2 a 5 e2 b 3 c2 b 3 d2 b 3 e2 b 4 c2 b 4 d2 b 4 e2 b 5 c2 b 5 d2 b 5 e |
希望本文所述对大家java程序设计有所帮助。
原文链接：http://blog.csdn.net/buptdavid/article/details/45918647
