递归和循环两种方式实现未知维度集合的笛卡尔积

时间：2022-04-16 12:38:45

什么是笛卡尔积？

在数学中，两个集合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 import java.util.ArrayList;  
  2 import java.util.Arrays;  
  3 import java.util.List;  
  4   
  5 /** 
  6  * 循环和递归两种方式实现未知维度集合的笛卡尔积 
  7  * Created on 2015-05-22 
  8  * @author luweijie 
  9  */  
 10 public class Descartes {  
 11   
 12     /** 
 13      * 递归实现dimValue中的笛卡尔积，结果放在result中 
 14      * @param dimValue 原始数据 
 15      * @param result 结果数据 
 16      * @param layer dimValue的层数 
 17      * @param curList 每次笛卡尔积的结果 
 18      */  
 19     private static void recursive (List<List<String>> dimValue, List<List<String>> result, int layer, List<String> curList) {  
 20         if (layer < dimValue.size() - 1) {  
 21             if (dimValue.get(layer).size() == 0) {  
 22                 recursive(dimValue, result, layer + 1, curList);  
 23             } else {  
 24                 for (int i = 0; i < dimValue.get(layer).size(); i++) {  
 25                     List<String> list = new ArrayList<String>(curList);  
 26                     list.add(dimValue.get(layer).get(i));  
 27                     recursive(dimValue, result, layer + 1, list);  
 28                 }  
 29             }  
 30         } else if (layer == dimValue.size() - 1) {  
 31             if (dimValue.get(layer).size() == 0) {  
 32                 result.add(curList);  
 33             } else {  
 34                 for (int i = 0; i < dimValue.get(layer).size(); i++) {  
 35                     List<String> list = new ArrayList<String>(curList);  
 36                     list.add(dimValue.get(layer).get(i));  
 37                     result.add(list);  
 38                 }  
 39             }  
 40         }  
 41     }  
 42   
 43     /** 
 44      * 循环实现dimValue中的笛卡尔积，结果放在result中 
 45      * @param dimValue 原始数据 
 46      * @param result 结果数据 
 47      */  
 48     private static void circulate (List<List<String>> dimValue, List<List<String>> result) {  
 49         int total = 1;  
 50         for (List<String> list : dimValue) {  
 51             total *= list.size();  
 52         }  
 53         String[] myResult = new String[total];  
 54   
 55         int itemLoopNum = 1;  
 56         int loopPerItem = 1;  
 57         int now = 1;  
 58         for (List<String> list : dimValue) {  
 59             now *= list.size();  
 60   
 61             int index = 0;  
 62             int currentSize = list.size();  
 63   
 64             itemLoopNum = total / now;  
 65             loopPerItem = total / (itemLoopNum * currentSize);  
 66             int myIndex = 0;  
 67   
 68             for (String string : list) {  
 69                 for (int i = 0; i < loopPerItem; i++) {  
 70                     if (myIndex == list.size()) {  
 71                         myIndex = 0;  
 72                     }  
 73   
 74                     for (int j = 0; j < itemLoopNum; j++) {  
 75                         myResult[index] = (myResult[index] == null? "" : myResult[index] + ",") + list.get(myIndex);  
 76                         index++;  
 77                     }  
 78                     myIndex++;  
 79                 }  
 80   
 81             }  
 82         }  
 83   
 84         List<String> stringResult = Arrays.asList(myResult);  
 85         for (String string : stringResult) {  
 86             String[] stringArray = string.split(",");  
 87             result.add(Arrays.asList(stringArray));  
 88         }  
 89     }  
 90   
 91     /** 
 92      * 程序入口 
 93      * @param args 
 94      */  
 95     public static void main (String[] args) {  
 96         List<String> list1 = new ArrayList<String>();  
 97         list1.add("1");  
 98         list1.add("2");  
 99   
100         List<String> list2 = new ArrayList<String>();  
101         list2.add("a");  
102         list2.add("b");  
103   
104         List<String> list3 = new ArrayList<String>();  
105         list3.add("3");  
106         list3.add("4");  
107         list3.add("5");  
108   
109         List<String> list4 = new ArrayList<String>();  
110         list4.add("c");  
111         list4.add("d");  
112         list4.add("e");  
113   
114         List<List<String>> dimValue = new ArrayList<List<String>>();  
115         dimValue.add(list1);  
116         dimValue.add(list2);  
117         dimValue.add(list3);  
118         dimValue.add(list4);  
119   
120         List<List<String>> recursiveResult = new ArrayList<List<String>>();  
121         // 递归实现笛卡尔积  
122         recursive(dimValue, recursiveResult, 0, new ArrayList<String>());  
123   
124         System.out.println("递归实现笛卡尔乘积: 共 " + recursiveResult.size() + " 个结果");  
125         for (List<String> list : recursiveResult) {  
126             for (String string : list) {  
127                 System.out.print(string + " ");  
128             }  
129             System.out.println();  
130         }  
131   
132         List<List<String>> circulateResult = new ArrayList<List<String>>();  
133         circulate(dimValue, circulateResult);  
134         System.out.println("循环实现笛卡尔乘积: 共 " + circulateResult.size() + " 个结果");  
135         for (List<String> list : circulateResult) {  
136             for (String string : list) {  
137                 System.out.print(string + " ");  
138             }  
139             System.out.println();  
140         }  
141     }  
142 }  

转载 http://blog.csdn.net/buptdavid/article/details/45918647

 

标签：

相关文章