import java.util.ArrayList;
import java.util.Stack;
/**
*
* 實現(xiàn)笛卡爾乘積運算結(jié)果的輸出：
* {n1,n2...}*{m1,m2,m3..}*{p1,p2,p3...}*....
* 模型非常類似樹的先根遍歷算法或圖的深度優(yōu)先搜索算法(有些勉強),如果輸入是:
* {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出發(fā),訪問出來的模型就是一顆樹,root表示第一次層次.
* 每次從樹的第二層節(jié)點出發(fā)到樹的葉子節(jié)點結(jié)束,所訪問過的節(jié)點記錄就是一個笛卡爾乘積運算結(jié)果.
*
*/
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-----");
/**
* 當(dāng)樹的總層次數(shù)>1時,注意樹的總層次數(shù)=root.size()-1.
*/
if(root.size()>0){
/**
* 得到第二層次上所有的樹節(jié)點.
*/
ArrayList nodeList = (ArrayList) root.get(0);
/**
* stack主要用來記錄，一次從樹的第二層節(jié)點到樹的葉子節(jié)點的時候，所訪問過的所有節(jié)點.
*/
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());
}
/**
* 這個方法主要用來實現(xiàn)這種for的嵌套模型:
* for()
* for()
* for()
* for()
* ...
* @param root 表示整顆樹
* @param treeDepthCounter 記錄第幾層次,0表示第一層次,1表示第二層次,...
* @param nodeList 記錄在該樹的層次上所有節(jié)點,就比如第二層的所有節(jié)點是{n1,n2}
* @param stack 主要用來記錄，一次從樹的第二層節(jié)點到樹的葉子節(jié)點的時候，所訪問過的所有節(jié)點.
*/
public static void traverse(ArrayList root,int treeDepthCounter,ArrayList nodeList, Stack stack){
for (int i = 0; i < nodeList.size(); i++) {
/**
* 取得一個樹節(jié)點
*/
Object element = nodeList.get(i);
/**
* 訪問該層中的一個節(jié)點,記錄該節(jié)點
*/
stack.push(element);
/**
* root.size()=整顆樹所擁有的層次數(shù)-1
* treeDepthCounter >= root.size()-1 ,表示已經(jīng)到達(dá)樹的葉子節(jié)點.
*/
if( treeDepthCounter >= root.size()-1) {
/**
* 如果這次從樹的第二層節(jié)點到樹的葉子節(jié)點的時候結(jié)束，
* 那么打印此次搜索中訪問的所有節(jié)點,stack保存該次訪問過的所有節(jié)點
*/
Object[] one_traverse=new Object[root.size()];
/**
* 取出和打印當(dāng)前stack中的所有記錄,但是不破壞stack中的所有記錄.
*/
stack.copyInto(one_traverse);
printArrayList(one_traverse);
}else {
/**
* 開始訪問下一層次的樹,nextDeepCounter為下一層次的層次數(shù).
*/
int nextDeepCounter=treeDepthCounter+1;
/**
* 得到下一層次上所有的樹節(jié)點,比如第3層次上的樹節(jié)點是{m1,m2,m3}.
*/
ArrayList nextNodeList = (ArrayList) root.get(nextDeepCounter);
/**
* 開始訪問下一層次的樹節(jié)點.
*/
traverse(root,nextDeepCounter,nextNodeList,stack);
}
/**
* 當(dāng)該節(jié)點訪問結(jié)束時,從記錄中刪除該節(jié)點.
*/
stack.pop();
}
}
}
如果輸入內(nèi)容為：
{1}
{2,3}
{4,5,6,7}
{8,9}
輸出結(jié)果為：
{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}
如果輸入內(nèi)容為：
{1}
{2,1,3.3}
{4.4,5,6.5,7.0}
{8.2,9.1,java.lang.Object@3a803a80}
那么輸出結(jié)果為：
{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}