java笛卡尔积算法_Java 笛卡尔积算法的简单实现
笛卡尔积算法的Java实现:
(1)循环内,每次只有一列向下移一个单元格,就是CounterIndex指向的那列。
(2)如果该列到尾部了,则这列index重置为0,而CounterIndex则指向前一列,相当于进位,把前列的index加一。
(3)最后,由生成的行数来控制退出循环。
public class Test {
private static String[] aa = { “aa1”, “aa2” };
private static String[] bb = { “bb1”, “bb2”, “bb3” };
private static String[] cc = { “cc1”, “cc2”, “cc3”, “cc4” };
private static String[][] xyz = { aa, bb, cc };
private static int counterIndex = xyz.length – 1;
private static int[] counter = { 0, 0, 0 };
public static void main(String[] args) throws Exception {
for (int i = 0; i < aa.length * bb.length * cc.length; i++) {
System.out.print(aa[counter[0]]);
System.out.print(“\t”);
System.out.print(bb[counter[1]]);
System.out.print(“\t”);
System.out.print(cc[counter[2]]);
System.out.println();
handle();
}
}
public static void handle() {
counter[counterIndex]++;
if (counter[counterIndex] >= xyz[counterIndex].length) {
counter[counterIndex] = 0;
counterIndex–;
if (counterIndex >= 0) {
handle();
}
counterIndex = xyz.length – 1;
}
}
}
输出共2*3*4=24行:
aa1 bb1 cc1
aa1 bb1 cc2
aa1 bb1 cc3
aa1 bb1 cc4
aa1 bb2 cc1
aa1 bb2 cc2
aa1 bb2 cc3
aa1 bb2 cc4
aa1 bb3 cc1
aa1 bb3 cc2
aa1 bb3 cc3
aa1 bb3 cc4
aa2 bb1 cc1
aa2 bb1 cc2
aa2 bb1 cc3
aa2 bb1 cc4
aa2 bb2 cc1
aa2 bb2 cc2
aa2 bb2 cc3
aa2 bb2 cc4
aa2 bb3 cc1
aa2 bb3 cc2
aa2 bb3 cc3
aa2 bb3 cc4
——————————————————————————————————————————-
最近碰到了一个笛卡尔积的算法要求,比如传递过来的参数是”1,3,6,7==4,5,8,9==3,4==43,45,8,9==35,4″,则返回的是一个list,如[1,4,3,43,35][1,4,3,43,4][1,4,3,45,35]……,该list包含是4*4*2*4*2=256个元素,现在的思路是这样的:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class DescartesTest {
/**
* 获取N个集合的笛卡尔积
*
* 说明:假如传入的字符串为:”1,2,3==5,6==7,8″
* 转换成字符串数组为:[[1, 2, 3], [5, 6], [7, 8]]
* a=[1, 2, 3]
* b=[5, 6]
* c=[7, 8]
* 其大小分别为:a_length=3,b_length=2,c_length=2,
* 目标list的总大小为:totalSize=3*2*2 = 12
* 对每个子集a,b,c,进行循环次数=总记录数/(元素个数*后续集合的笛卡尔积个数)
* 对a中的每个元素循环次数=总记录数/(元素个数*后续集合的笛卡尔积个数)=12/(3*4)=1次,每个元素每次循环打印次数:后续集合的笛卡尔积个数=2*2个
* 对b中的每个元素循环次数=总记录数/(元素个数*后续集合的笛卡尔积个数)=12/(2*2)=3次,每个元素每次循环打印次数:后续集合的笛卡尔积个数=2个
* 对c中的每个元素循环次数=总记录数/(元素个数*后续集合的笛卡尔积个数)=12/(2*1)=6次,每个元素每次循环打印次数:后续集合的笛卡尔积个数=1个
*
* 运行结果:
* [[1, 2, 3], [5, 6], [7, 8]]
1,5,7,
1,5,8,
1,6,7,
1,6,8,
2,5,7,
2,5,8,
2,6,7,
2,6,8,
3,5,7,
3,5,8,
3,6,7,
3,6,8]
从结果中可以看到:
a中的每个元素每个元素循环1次,每次打印4个
b中的每个元素每个元素循环3次,每次打印2个
c中的每个元素每个元素循环6次,每次打印1个
*
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str =”1,3,6,7==4,5,8,9==3,4==43,45,8,9==35,4″;
List result = descartes(str);
System.out.println(result);
}
@SuppressWarnings(“rawtypes”)
public static List descartes(String str) {
String[] list = str.split(“==”);
List strs = new ArrayList();
for(int i=0;i
strs.add(Arrays.asList(list[i].split(“,”)));
}
System.out.println(strs);
int total = 1;
for(int i=0;i
total*=strs.get(i).size();
}
String[] mysesult = new String[total];
int now = 1;
//每个元素每次循环打印个数
int itemLoopNum = 1;
//每个元素循环的总次数
int loopPerItem =1;
for(int i=0;i
List temp = strs.get(i);
now = now*temp.size();
//目标数组的索引值
int index=0;
int currentSize = temp.size();
itemLoopNum = total/now;
loopPerItem = total/(itemLoopNum*currentSize);
int myindex = 0;
for(int j=0;j
//每个元素循环的总次数
for(int k=0;k
if(myindex==temp.size())
myindex=0;
//每个元素每次循环打印个数
for(int m=0;m
mysesult[index]=(mysesult[index]==null?””:mysesult[index]+”,”)+((String)temp.get(myindex));
index++;
}
myindex++;
}
}
}
return Arrays.asList(mysesult);
}
}
——————————————————————————————————————————-
递归:
public static void fn(List list,String[] arr,String str){
//迭代list
List li = new ArrayList();
for(int i=0;i
//取得当前的数组
if(i==list.indexOf(arr)){
//迭代数组
System.out.println(arr.length);
for(String st : arr){
st = str + st;
if(i
fn(list,list.get(i+1),st);
}else if(i==list.size()-1){
li.add(st);
}
}
}
}
for(int i = 0 ; i < li.size();i++ )
{
System.out.println(li.get(i));
}
}
大小: 16.8 KB
fn 函数循环是没有必要的啊,可以改成
protected static List fn(List list, Object[] arr, String result, String separator) {
//迭代list
List li = new ArrayList();
//取得当前的数组
int i = list.indexOf(arr);
//迭代数组
for (Object st : arr) {
if (StringUtils.isNotBlank(result)) {
st = result + separator + st;
}
if (i < list.size() – 1) {
li.addAll(fn(list, list.get(i + 1), st.toString(), separator));
} else if (i == list.size() – 1) {
li.add(st.toString());
}
}
return li;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/157687.html原文链接:https://javaforall.cn
相关文章
- 【算法】java 实现数组的反转
- java map 二维数组_Java二维数组实现简单Map
- protostuff java_Protostuff一键序列化工具、Protobuf JAVA实现
- java语言的特点_Java语言有什么特点?
- #Java算法设计与分析1–递归算法
- java实现四种常用排序算法
- java 随机数算法_Java随机数算法原理与实现方法实例详解
- 【说站】java泛型算法如何实现
- java实现递归树形结构_java递归算法经典实例
- java 舆情分析_基于Java实现网络舆情分析系统研究与实现.doc[通俗易懂]
- 一致性hash算法 java实现_信息的一致性
- Java 对称加密几种算法分别实现详解编程语言
- java实现排序算法:插入排序、选择排序、冒泡排序详解编程语言
- Java 冒泡排序算法实现详解编程语言
- Java学习笔记之九java二维数组及其多维数组的内存应用拓展延伸详解编程语言
- Java操作Oracle数据库:实现数据库连接与访问(java连接oracle数据库)
- Java连接SQL Server:实现数据库完美对接(java链接sqlserver)
- 使用Java连接SQL Server数据库,快速高效地管理数据(java连接sqlserver数据库)
- 基于Linux操作系统上实现 Java 编程(linux r java)
- Java革命Oracle旗下的程序设计利器(java简介oracle)
- Java模拟Oracle实现稳定数据库性能(java模仿oracle)
- 实现基于Redis的分布式锁Java实现(redis锁java代码)
- Java消息处理实践突破性技术Redis(redis消息 java)
- 全面解析java中的hashtable
- 冒泡排序算法原理及JAVA实现代码