您好,登錄后才能下訂單哦!
這篇文章主要介紹Java基于遞歸和循環(huán)如何實現(xiàn)未知維度集合的笛卡爾積算法,文中介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們一定要看完!
什么是笛卡爾積?
在數(shù)學中,兩個集合X和Y的笛卡兒積(Cartesian product),又稱直積,表示為X × Y,第一個對象是X的成員而第二個對象是Y的所有可能有序?qū)Φ钠渲幸粋€成員。
假設(shè)集合A={a,b},集合B={0,1,2},則兩個集合的笛卡爾積為{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}。
如何用程序算法實現(xiàn)笛卡爾積?
如果編程前已知集合的數(shù)量,通過程序的多次循環(huán)即可得出笛卡爾積。但是如果編程前不知道集合的數(shù)量,如何得到笛卡爾積哪?比如集合表示List < List<String>> list
;這個list在編程前l(fā)ist的數(shù)量是未知的。下面的代碼使用遞歸和循環(huán)兩種方法實現(xiàn)未知維度集合的笛卡爾積:
import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 循環(huán)和遞歸兩種方式實現(xiàn)未知維度集合的笛卡爾積 * Created on 2015-05-22 * @author luweijie */ public class Descartes { /** * 遞歸實現(xiàn)dimValue中的笛卡爾積,結(jié)果放在result中 * @param dimValue 原始數(shù)據(jù) * @param result 結(jié)果數(shù)據(jù) * @param layer dimValue的層數(shù) * @param curList 每次笛卡爾積的結(jié)果 */ 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); } } } } /** * 循環(huán)實現(xiàn)dimValue中的笛卡爾積,結(jié)果放在result中 * @param dimValue 原始數(shù)據(jù) * @param result 結(jié)果數(shù)據(jù) */ 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>>(); // 遞歸實現(xiàn)笛卡爾積 recursive(dimValue, recursiveResult, 0, new ArrayList<String>()); System.out.println("遞歸實現(xiàn)笛卡爾乘積: 共 " + recursiveResult.size() + " 個結(jié)果"); 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("循環(huán)實現(xiàn)笛卡爾乘積: 共 " + circulateResult.size() + " 個結(jié)果"); for (List<String> list : circulateResult) { for (String string : list) { System.out.print(string + " "); } System.out.println(); } } }
輸出結(jié)果是:
遞歸實現(xiàn)笛卡爾乘積: 共 36 個結(jié)果 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 循環(huán)實現(xiàn)笛卡爾乘積: 共 36 個結(jié)果 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
以上是“Java基于遞歸和循環(huán)如何實現(xiàn)未知維度集合的笛卡爾積算法”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。