/**
*
* 瀹炵幇絎涘崱灝斾箻縐繍綆楃粨鏋滅殑杈撳嚭錛?br /> * {n1,n2...}*{m1,m2,m3..}*{p1,p2,p3...}*....
* 妯″瀷闈炲父綾諱技鏍戠殑鍏堟牴閬嶅巻綆楁硶鎴栧浘鐨勬繁搴︿紭鍏堟悳绱㈢畻娉?鏈変簺鍕夊己),濡傛灉杈撳叆鏄?
* {n1,n2}*{m1,m2,m3}*{p1,p2,p3}
* 閭ｄ箞鎼滅儲妯″瀷鏄?
* root-->n1--->m1--->p1
* --->p2
* --->p3
* --->m2--->p1
* --->p2
* --->p3
* --->m3--->p1
* --->p2
* --->p3
* root-->n2--->m1--->p1
* --->p2
* --->p3
* --->m2--->p1
* --->p2
* --->p3
* --->m3--->p1
* --->p2
* --->p3
* 浠庝笂闈㈠彲浠ョ湅鍒頒粠root鍑哄彂,璁塊棶鍑烘潵鐨勬ā鍨嬪氨鏄竴棰楁爲,root琛ㄧず絎竴嬈″眰嬈?
* 姣忔浠庢爲鐨勭浜屽眰鑺傜偣鍑哄彂鍒版爲鐨勫彾瀛愯妭鐐圭粨鏉?鎵璁塊棶榪囩殑鑺傜偣璁板綍灝辨槸涓涓瑳鍗″皵涔樼Н榪愮畻緇撴灉.
*
*/
public class DescartesMultiplication {
public static void main(String[] args) {
//initiate all of data:
ArrayList list1= new ArrayList();
ArrayList list2= new ArrayList();
ArrayList list3= new ArrayList();
ArrayList list4= new ArrayList();
ArrayList root= new ArrayList();
// list1.add("1");
// list2.add("2");
// list2.add("3");
// list3.add("4");
// list3.add("5");
// list3.add("6");
// list3.add("7");
// list4.add("8");
// list4.add("9");
list1.add(1);
list2.add(2);
list2.add("1");
list2.add(3.3);
list3.add(4.4);
list3.add(5);
list3.add(6.5);
list3.add(7.0);
list4.add(8.2);
list4.add(9.1);
list4.add(new Object());
root.add(list1);
root.add(list2);
root.add(list3);
root.add(list4);
//print all of data:
for (int i = 0; i < root.size(); i++) {
ArrayList list=new ArrayList();
ArrayList item = (ArrayList) root.get(i);
for (int j = 0; j < item.size(); j++) {
Object element = item.get(j);
list.add(element);
}
printArrayList(list);
}
//begin to a depth-first search traverse from the root node.
System.out.println("-----Below is a result of DescartesMultiplication-----");
/**
* 褰撴爲鐨勬誨眰嬈℃暟>1鏃?娉ㄦ剰鏍戠殑鎬誨眰嬈℃暟=root.size()-1.
*/
if(root.size()>0){
/**
* 寰楀埌絎簩灞傛涓婃墍鏈夌殑鏍戣妭鐐?
*/
ArrayList nodeList = (ArrayList) root.get(0);
/**
* stack涓昏鐢ㄦ潵璁板綍錛屼竴嬈′粠鏍戠殑絎簩灞傝妭鐐瑰埌鏍戠殑鍙跺瓙鑺傜偣鐨勬椂鍊欙紝鎵璁塊棶榪囩殑鎵鏈夎妭鐐?
*/
Stack<String> stack= new Stack();
/**
* 浠庢爲鐨勭浜屽眰嬈″紑濮嬪厛搴忛亶鍘嗘暣棰楁爲.
*/
traverse(root,0,nodeList,stack);
}
}
public static void printArrayList(ArrayList list){
StringBuffer sb=new StringBuffer();
sb.append("{");
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i).toString()+",");
}
sb.deleteCharAt(sb.length()-1);
sb.append("}");
System.out.println(sb.toString());
}
public static void printArrayList(Object[] array){
StringBuffer sb=new StringBuffer();
sb.append("{");
for (int i = 0; i < array.length; i++) {
sb.append(array[i].toString()+",");
}
sb.deleteCharAt(sb.length()-1);
sb.append("}");
System.out.println(sb.toString());
}
/**
* 榪欎釜鏂規硶涓昏鐢ㄦ潵瀹炵幇榪欑for鐨勫祵濂楁ā鍨?
* for()
* for()
* for()
* for()
* ...
* @param root 琛ㄧず鏁撮鏍?br /> * @param treeDepthCounter 璁板綍絎嚑灞傛,0琛ㄧず絎竴灞傛,1琛ㄧず絎簩灞傛,...
* @param nodeList 璁板綍鍦ㄨ鏍戠殑灞傛涓婃墍鏈夎妭鐐?灝辨瘮濡傜浜屽眰鐨勬墍鏈夎妭鐐規槸{n1,n2}
* @param stack 涓昏鐢ㄦ潵璁板綍錛屼竴嬈′粠鏍戠殑絎簩灞傝妭鐐瑰埌鏍戠殑鍙跺瓙鑺傜偣鐨勬椂鍊欙紝鎵璁塊棶榪囩殑鎵鏈夎妭鐐?
*/
public static void traverse(ArrayList root,int treeDepthCounter,ArrayList nodeList, Stack stack){
for (int i = 0; i < nodeList.size(); i++) {
/**
* 鍙栧緱涓涓爲鑺傜偣
*/
Object element = nodeList.get(i);
/**
* 璁塊棶璇ュ眰涓殑涓涓妭鐐?璁板綍璇ヨ妭鐐?br /> */
stack.push(element);
/**
* root.size()=鏁撮鏍戞墍鎷ユ湁鐨勫眰嬈℃暟-1
* treeDepthCounter >= root.size()-1 ,琛ㄧず宸茬粡鍒拌揪鏍戠殑鍙跺瓙鑺傜偣.
*/
if( treeDepthCounter >= root.size()-1) {
/**
* 濡傛灉榪欐浠庢爲鐨勭浜屽眰鑺傜偣鍒版爲鐨勫彾瀛愯妭鐐圭殑鏃跺欑粨鏉燂紝
* 閭ｄ箞鎵撳嵃姝ゆ鎼滅儲涓闂殑鎵鏈夎妭鐐?stack淇濆瓨璇ユ璁塊棶榪囩殑鎵鏈夎妭鐐?br /> */
Object[] one_traverse=new Object[root.size()];
/**
* 鍙栧嚭鍜屾墦鍗板綋鍓峴tack涓殑鎵鏈夎褰?浣嗘槸涓嶇牬鍧弒tack涓殑鎵鏈夎褰?
*/
stack.copyInto(one_traverse);
printArrayList(one_traverse);
}else {
/**
* 寮濮嬭闂笅涓灞傛鐨勬爲,nextDeepCounter涓轟笅涓灞傛鐨勫眰嬈℃暟.
*/
int nextDeepCounter=treeDepthCounter+1;
/**
* 寰楀埌涓嬩竴灞傛涓婃墍鏈夌殑鏍戣妭鐐?姣斿絎?灞傛涓婄殑鏍戣妭鐐規槸{m1,m2,m3}.
*/
ArrayList nextNodeList = (ArrayList) root.get(nextDeepCounter);
/**
* 寮濮嬭闂笅涓灞傛鐨勬爲鑺傜偣.
*/
traverse(root,nextDeepCounter,nextNodeList,stack);
}
/**
* 褰撹鑺傜偣璁塊棶緇撴潫鏃?浠庤褰曚腑鍒犻櫎璇ヨ妭鐐?
*/
stack.pop();
}
}
}
濡傛灉杈撳叆鍐呭涓猴細
{1}
{2,3}
{4,5,6,7}
{8,9}
杈撳嚭緇撴灉涓猴細
{1,2,4,8}
{1,2,4,9}
{1,2,5,8}
{1,2,5,9}
{1,2,6,8}
{1,2,6,9}
{1,2,7,8}
{1,2,7,9}
{1,3,4,8}
{1,3,4,9}
{1,3,5,8}
{1,3,5,9}
{1,3,6,8}
{1,3,6,9}
{1,3,7,8}
{1,3,7,9}
濡傛灉杈撳叆鍐呭涓猴細
{1}
{2,1,3.3}
{4.4,5,6.5,7.0}
{8.2,9.1,java.lang.Object@3a803a80}
閭ｄ箞杈撳嚭緇撴灉涓猴細
{1,2,4.4,8.2}
{1,2,4.4,9.1}
{1,2,4.4,java.lang.Object@3a803a80}
{1,2,5,8.2}
{1,2,5,9.1}
{1,2,5,java.lang.Object@3a803a80}
{1,2,6.5,8.2}
{1,2,6.5,9.1}
{1,2,6.5,java.lang.Object@3a803a80}
{1,2,7.0,8.2}
{1,2,7.0,9.1}
{1,2,7.0,java.lang.Object@3a803a80}
{1,1,4.4,8.2}
{1,1,4.4,9.1}
{1,1,4.4,java.lang.Object@3a803a80}
{1,1,5,8.2}
{1,1,5,9.1}
{1,1,5,java.lang.Object@3a803a80}
{1,1,6.5,8.2}
{1,1,6.5,9.1}
{1,1,6.5,java.lang.Object@3a803a80}
{1,1,7.0,8.2}
{1,1,7.0,9.1}
{1,1,7.0,java.lang.Object@3a803a80}
{1,3.3,4.4,8.2}
{1,3.3,4.4,9.1}
{1,3.3,4.4,java.lang.Object@3a803a80}
{1,3.3,5,8.2}
{1,3.3,5,9.1}
{1,3.3,5,java.lang.Object@3a803a80}
{1,3.3,6.5,8.2}
{1,3.3,6.5,9.1}
{1,3.3,6.5,java.lang.Object@3a803a80}
{1,3.3,7.0,8.2}
{1,3.3,7.0,9.1}
{1,3.3,7.0,java.lang.Object@3a803a80}
]]>