Java implements an example of cartesian product algorithm for unknown dimensional sets based on recursion and loop
- 2020-12-10 00:41:19
- OfStack
This paper illustrates Java's implementation of cartesian product of unknown dimensional sets based on recursion and loop. To share for your reference, the details are as follows:
What is the Cartesian product?
In mathematics, the Cartesian product, or direct product, of two sets X and Y is represented as X × Y, with the first object a member of X and the second object a member of all possible ordered pairs of Y.
Suppose set A={a,b}, set B={0,1,2}, then the cartesian product of two sets is {(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}.
How to realize Cartesian product with program algorithm?
If the number of sets is known before programming, the Cartesian product can be obtained through multiple loops of the program. But if you don't know the number of sets before you program, how do you get the Cartesian product? Like the set representation
List < List<String>> list
; The number of this list list before programming is unknown. The following code implements the Cartesian product of an unknown set of dimensions using recursion and looping:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* The cartesian product of an unknown set of dimensions is realized in two ways: loop and recursion
* Created on 2015-05-22
* @author luweijie
*/
public class Descartes {
/**
* The recursive implementation dimValue Cartesian product, the result of which is result In the
* @param dimValue The original data
* @param result The resulting data
* @param layer dimValue The number of layers
* @param curList Every cartesian product
*/
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);
}
}
}
}
/**
* Cycle to achieve dimValue Cartesian product, the result of which is result In the
* @param dimValue The original data
* @param result The resulting data
*/
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));
}
}
/**
* Program entrance
* @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>>();
// We recursively implement the Cartesian product
recursive(dimValue, recursiveResult, 0, new ArrayList<String>());
System.out.println(" We recursively implement the Cartesian product : A total of " + recursiveResult.size() + " results ");
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(" The cycle implements the Cartesian product : A total of " + circulateResult.size() + " results ");
for (List<String> list : circulateResult) {
for (String string : list) {
System.out.print(string + " ");
}
System.out.println();
}
}
}
The output result is:
We recursively implement the Cartesian product : A total of 36 results
1 a 3 c
1 a 3 d
1 a 3 e
1 a 4 c
1 a 4 d
1 a 4 e
1 a 5 c
1 a 5 d
1 a 5 e
1 b 3 c
1 b 3 d
1 b 3 e
1 b 4 c
1 b 4 d
1 b 4 e
1 b 5 c
1 b 5 d
1 b 5 e
2 a 3 c
2 a 3 d
2 a 3 e
2 a 4 c
2 a 4 d
2 a 4 e
2 a 5 c
2 a 5 d
2 a 5 e
2 b 3 c
2 b 3 d
2 b 3 e
2 b 4 c
2 b 4 d
2 b 4 e
2 b 5 c
2 b 5 d
2 b 5 e
The cycle implements the Cartesian product : A total of 36 results
1 a 3 c
1 a 3 d
1 a 3 e
1 a 4 c
1 a 4 d
1 a 4 e
1 a 5 c
1 a 5 d
1 a 5 e
1 b 3 c
1 b 3 d
1 b 3 e
1 b 4 c
1 b 4 d
1 b 4 e
1 b 5 c
1 b 5 d
1 b 5 e
2 a 3 c
2 a 3 d
2 a 3 e
2 a 4 c
2 a 4 d
2 a 4 e
2 a 5 c
2 a 5 d
2 a 5 e
2 b 3 c
2 b 3 d
2 b 3 e
2 b 4 c
2 b 4 d
2 b 4 e
2 b 5 c
2 b 5 d
2 b 5 e
For more information about java algorithm, please refer to Java Data Structure and Algorithm Tutorial, Java Operation DOM Node Skills Summary, Java File and Directory Operation Skills Summary and Java Cache Operation Skills Summary.
I hope this article has been helpful in java programming.