Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例
本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积。分享给大家供大家参考，具体如下：
什么是笛卡尔积？
在数学中，两个集合X和Y的笛卡儿积（Cartesianproduct），又称直积，表示为X×Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。
假设集合A={a,b}，集合B={0,1,2}，则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1),(b,2)}。
如何用程序算法实现笛卡尔积？
如果编程前已知集合的数量，通过程序的多次循环即可得出笛卡尔积。但是如果编程前不知道集合的数量，如何得到笛卡尔积哪？比如集合表示List
importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.List;
/**
*循环和递归两种方式实现未知维度集合的笛卡尔积
*Createdon2015-05-22
*@authorluweijie
*/
publicclassDescartes{
/**
*递归实现dimValue中的笛卡尔积，结果放在result中
*@paramdimValue原始数据
*@paramresult结果数据
*@paramlayerdimValue的层数
*@paramcurList每次笛卡尔积的结果
*/
privatestaticvoidrecursive(List>dimValue,List>result,intlayer,ListcurList){
if(layerlist=newArrayList(curList);
list.add(dimValue.get(layer).get(i));
recursive(dimValue,result,layer+1,list);
}
}
}elseif(layer==dimValue.size()-1){
if(dimValue.get(layer).size()==0){
result.add(curList);
}else{
for(inti=0;ilist=newArrayList(curList);
list.add(dimValue.get(layer).get(i));
result.add(list);
}
}
}
}
/**
*循环实现dimValue中的笛卡尔积，结果放在result中
*@paramdimValue原始数据
*@paramresult结果数据
*/
privatestaticvoidcirculate(List>dimValue,List>result){
inttotal=1;
for(Listlist:dimValue){
total*=list.size();
}
String[]myResult=newString[total];
intitemLoopNum=1;
intloopPerItem=1;
intnow=1;
for(Listlist:dimValue){
now*=list.size();
intindex=0;
intcurrentSize=list.size();
itemLoopNum=total/now;
loopPerItem=total/(itemLoopNum*currentSize);
intmyIndex=0;
for(Stringstring:list){
for(inti=0;istringResult=Arrays.asList(myResult);
for(Stringstring:stringResult){
String[]stringArray=string.split(",");
result.add(Arrays.asList(stringArray));
}
}
/**
*程序入口
*@paramargs
*/
publicstaticvoidmain(String[]args){
Listlist1=newArrayList();
list1.add("1");
list1.add("2");
Listlist2=newArrayList();
list2.add("a");
list2.add("b");
Listlist3=newArrayList();
list3.add("3");
list3.add("4");
list3.add("5");
Listlist4=newArrayList();
list4.add("c");
list4.add("d");
list4.add("e");
List>dimValue=newArrayList>();
dimValue.add(list1);
dimValue.add(list2);
dimValue.add(list3);
dimValue.add(list4);
List>recursiveResult=newArrayList>();
//递归实现笛卡尔积
recursive(dimValue,recursiveResult,0,newArrayList());
System.out.println("递归实现笛卡尔乘积:共"+recursiveResult.size()+"个结果");
for(Listlist:recursiveResult){
for(Stringstring:list){
System.out.print(string+"");
}
System.out.println();
}
List>circulateResult=newArrayList>();
circulate(dimValue,circulateResult);
System.out.println("循环实现笛卡尔乘积:共"+circulateResult.size()+"个结果");
for(Listlist:circulateResult){
for(Stringstring:list){
System.out.print(string+"");
}
System.out.println();
}
}
}
输出结果是：
递归实现笛卡尔乘积:共36个结果 1a3c 1a3d 1a3e 1a4c 1a4d 1a4e 1a5c 1a5d 1a5e 1b3c 1b3d 1b3e 1b4c 1b4d 1b4e 1b5c 1b5d 1b5e 2a3c 2a3d 2a3e 2a4c 2a4d 2a4e 2a5c 2a5d 2a5e 2b3c 2b3d 2b3e 2b4c 2b4d 2b4e 2b5c 2b5d 2b5e 循环实现笛卡尔乘积:共36个结果 1a3c 1a3d 1a3e 1a4c 1a4d 1a4e 1a5c 1a5d 1a5e 1b3c 1b3d 1b3e 1b4c 1b4d 1b4e 1b5c 1b5d 1b5e 2a3c 2a3d 2a3e 2a4c 2a4d 2a4e 2a5c 2a5d 2a5e 2b3c 2b3d 2b3e 2b4c 2b4d 2b4e 2b5c 2b5d 2b5e
更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。