This article describes the Cartesian product of Java implementing the collection of unknown dimensions based on recursion and loop. Share it for your reference, as follows:
What is Cartesian product?
In mathematics, the Cartesian product of two sets X and Y, also known as direct product, is expressed as X × Y, the first object is a member of X and the second object is one of all possible ordered pairs of Y.
Assuming that set A={a,b} and set B={0,1,2}, then the Cartesian product of the two sets is {(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}.
How to use program algorithms to implement Cartesian product?
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 programming, how can you get the Cartesian product? For example, a collection represents List < List<String>> list ; the number of lists before programming is unknown. The following code uses two methods of recursion and loop to implement the Cartesian product of unknown dimension sets:
import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * Two ways to realize the Cartesian product of unknown dimension sets* Created on 2015-05-22 * @author luweijie */public class Descartes { /** * Recursively implement the Cartesian product in dimValue, and the result is placed in the result* @param dimValue Raw data* @param result Result data* @param layer dimValue number of layers* @param curList The result of each 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); } } } } /** * Loop to implement the Cartesian product in dimValue, and the result is placed in result* @param dimValue Raw data* @param result Result data*/ private static void circuit (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 entry* @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>>(); // Recursively implement the Cartesian product recursive(dimValue, recursiveResult, 0, new ArrayList<String>()); System.out.println("Recursively implements the Cartesian product: total " + recursiveResult.size() + " results"); for (List<String> list : recursiveResult) { for (String string : list) { System.out.print(string + " "); } System.out.println(); } List<List<String>> circuitResult = new ArrayList<List<String>>(); circuit(dimValue, circuitResult); System.out.println("Loop implements Cartesian product: total" + circuitResult.size() + "result"); for (List<String> list : circuitResult) { for (String string : list) { System.out.print(string + " "); } System.out.println(); } }}The output result is:
Recursively implementing the Cartesian product: A total of 36 results1 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 loop implementing the Cartesian product: A total of 36 results1 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
For more information about Java algorithms, readers who are interested in this site can view the topics: "Java Data Structure and Algorithm Tutorial", "Summary of Java Operation DOM Node Tips", "Summary of Java File and Directory Operation Tips" and "Summary of Java Cache Operation Tips"
I hope this article will be helpful to everyone's Java programming.