Java笛卡尔积算法原理与实现方法详解
作者:coconut_zhang 发布时间:2023-11-18 22:08:17
本文实例讲述了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<String> result = descartes(str);
System.out.println(result);
}
@SuppressWarnings("rawtypes")
public static List<String> descartes(String str) {
String[] list = str.split("==");
List<List> strs = new ArrayList<List>();
for(int i=0;i<list.length;i++){
strs.add(Arrays.asList(list[i].split(",")));
}
System.out.println(strs);
int total = 1;
for(int i=0;i<strs.size();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<strs.size();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<temp.size();j++){
//每个元素循环的总次数
for(int k=0;k<loopPerItem;k++){
if(myindex==temp.size())
myindex=0;
//每个元素每次循环打印个数
for(int m=0;m<itemLoopNum;m++){
mysesult[index]=(mysesult[index]==null?"":mysesult[index]+",")+((String)temp.get(myindex));
index++;
}
myindex++;
}
}
}
return Arrays.asList(mysesult);
}
}
运行结果输出:
[[1, 3, 6, 7], [4, 5, 8, 9], [3, 4], [43, 45, 8, 9], [35, 4]]
[1,4,3,43,35, 1,4,3,43,4, 1,4,3,45,35, 1,4,3,45,4, 1,4,3,8,35, 1,4,3,8,4, 1,4,3,9,35, 1,4,3,9,4, 1,4,4,43,35, 1,4,4,43,4, 1,4,4,45,35, 1,4,4,45,4, 1,4,4,8,35, 1,4,4,8,4, 1,4,4,9,35, 1,4,4,9,4, 1,5,3,43,35, 1,5,3,43,4, 1,5,3,45,35, 1,5,3,45,4, 1,5,3,8,35, 1,5,3,8,4, 1,5,3,9,35, 1,5,3,9,4, 1,5,4,43,35, 1,5,4,43,4, 1,5,4,45,35, 1,5,4,45,4, 1,5,4,8,35, 1,5,4,8,4, 1,5,4,9,35, 1,5,4,9,4, 1,8,3,43,35, 1,8,3,43,4, 1,8,3,45,35, 1,8,3,45,4, 1,8,3,8,35, 1,8,3,8,4, 1,8,3,9,35, 1,8,3,9,4, 1,8,4,43,35, 1,8,4,43,4, 1,8,4,45,35, 1,8,4,45,4, 1,8,4,8,35, 1,8,4,8,4, 1,8,4,9,35, 1,8,4,9,4, 1,9,3,43,35, 1,9,3,43,4, 1,9,3,45,35, 1,9,3,45,4, 1,9,3,8,35, 1,9,3,8,4, 1,9,3,9,35, 1,9,3,9,4, 1,9,4,43,35, 1,9,4,43,4, 1,9,4,45,35, 1,9,4,45,4, 1,9,4,8,35, 1,9,4,8,4, 1,9,4,9,35, 1,9,4,9,4, 3,4,3,43,35, 3,4,3,43,4, 3,4,3,45,35, 3,4,3,45,4, 3,4,3,8,35, 3,4,3,8,4, 3,4,3,9,35, 3,4,3,9,4, 3,4,4,43,35, 3,4,4,43,4, 3,4,4,45,35, 3,4,4,45,4, 3,4,4,8,35, 3,4,4,8,4, 3,4,4,9,35, 3,4,4,9,4, 3,5,3,43,35, 3,5,3,43,4, 3,5,3,45,35, 3,5,3,45,4, 3,5,3,8,35, 3,5,3,8,4, 3,5,3,9,35, 3,5,3,9,4, 3,5,4,43,35, 3,5,4,43,4, 3,5,4,45,35, 3,5,4,45,4, 3,5,4,8,35, 3,5,4,8,4, 3,5,4,9,35, 3,5,4,9,4, 3,8,3,43,35, 3,8,3,43,4, 3,8,3,45,35, 3,8,3,45,4, 3,8,3,8,35, 3,8,3,8,4, 3,8,3,9,35, 3,8,3,9,4, 3,8,4,43,35, 3,8,4,43,4, 3,8,4,45,35, 3,8,4,45,4, 3,8,4,8,35, 3,8,4,8,4, 3,8,4,9,35, 3,8,4,9,4, 3,9,3,43,35, 3,9,3,43,4, 3,9,3,45,35, 3,9,3,45,4, 3,9,3,8,35, 3,9,3,8,4, 3,9,3,9,35, 3,9,3,9,4, 3,9,4,43,35, 3,9,4,43,4, 3,9,4,45,35, 3,9,4,45,4, 3,9,4,8,35, 3,9,4,8,4, 3,9,4,9,35, 3,9,4,9,4, 6,4,3,43,35, 6,4,3,43,4, 6,4,3,45,35, 6,4,3,45,4, 6,4,3,8,35, 6,4,3,8,4, 6,4,3,9,35, 6,4,3,9,4, 6,4,4,43,35, 6,4,4,43,4, 6,4,4,45,35, 6,4,4,45,4, 6,4,4,8,35, 6,4,4,8,4, 6,4,4,9,35, 6,4,4,9,4, 6,5,3,43,35, 6,5,3,43,4, 6,5,3,45,35, 6,5,3,45,4, 6,5,3,8,35, 6,5,3,8,4, 6,5,3,9,35, 6,5,3,9,4, 6,5,4,43,35, 6,5,4,43,4, 6,5,4,45,35, 6,5,4,45,4, 6,5,4,8,35, 6,5,4,8,4, 6,5,4,9,35, 6,5,4,9,4, 6,8,3,43,35, 6,8,3,43,4, 6,8,3,45,35, 6,8,3,45,4, 6,8,3,8,35, 6,8,3,8,4, 6,8,3,9,35, 6,8,3,9,4, 6,8,4,43,35, 6,8,4,43,4, 6,8,4,45,35, 6,8,4,45,4, 6,8,4,8,35, 6,8,4,8,4, 6,8,4,9,35, 6,8,4,9,4, 6,9,3,43,35, 6,9,3,43,4, 6,9,3,45,35, 6,9,3,45,4, 6,9,3,8,35, 6,9,3,8,4, 6,9,3,9,35, 6,9,3,9,4, 6,9,4,43,35, 6,9,4,43,4, 6,9,4,45,35, 6,9,4,45,4, 6,9,4,8,35, 6,9,4,8,4, 6,9,4,9,35, 6,9,4,9,4, 7,4,3,43,35, 7,4,3,43,4, 7,4,3,45,35, 7,4,3,45,4, 7,4,3,8,35, 7,4,3,8,4, 7,4,3,9,35, 7,4,3,9,4, 7,4,4,43,35, 7,4,4,43,4, 7,4,4,45,35, 7,4,4,45,4, 7,4,4,8,35, 7,4,4,8,4, 7,4,4,9,35, 7,4,4,9,4, 7,5,3,43,35, 7,5,3,43,4, 7,5,3,45,35, 7,5,3,45,4, 7,5,3,8,35, 7,5,3,8,4, 7,5,3,9,35, 7,5,3,9,4, 7,5,4,43,35, 7,5,4,43,4, 7,5,4,45,35, 7,5,4,45,4, 7,5,4,8,35, 7,5,4,8,4, 7,5,4,9,35, 7,5,4,9,4, 7,8,3,43,35, 7,8,3,43,4, 7,8,3,45,35, 7,8,3,45,4, 7,8,3,8,35, 7,8,3,8,4, 7,8,3,9,35, 7,8,3,9,4, 7,8,4,43,35, 7,8,4,43,4, 7,8,4,45,35, 7,8,4,45,4, 7,8,4,8,35, 7,8,4,8,4, 7,8,4,9,35, 7,8,4,9,4, 7,9,3,43,35, 7,9,3,43,4, 7,9,3,45,35, 7,9,3,45,4, 7,9,3,8,35, 7,9,3,8,4, 7,9,3,9,35, 7,9,3,9,4, 7,9,4,43,35, 7,9,4,43,4, 7,9,4,45,35, 7,9,4,45,4, 7,9,4,8,35, 7,9,4,8,4, 7,9,4,9,35, 7,9,4,9,4]
递归算法:
public static void fn(List<String[]> list,String[] arr,String str){
//迭代list
List<String> li = new ArrayList<String>();
for(int i=0;i<list.size();i++){
//取得当前的数组
if(i==list.indexOf(arr)){
//迭代数组
System.out.println(arr.length);
for(String st : arr){
st = str + st;
if(i<list.size()-1){
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));
}
}
希望本文所述对大家java程序设计有所帮助。
来源:http://coconut-zhang.iteye.com/blog/1709547
猜你喜欢
- spring boot是个好东西,可以不用容器直接在main方法中启动,而且无需配置文件,方便快速搭建环境。可是当我们要同时启动2个spri
- 第1部分 List概括List的框架图List 是一个接口,它继承于Collection的接口。它代表着有序的队列。AbstractList
- 常见尺寸单位Android开发中的常用尺寸单位有如下几种:dp (dip)pxptinchsp算不知道确切含义,相信对于以上这几种尺寸单位大
- typora-copy-images-to: ./一键清除maven仓库中下载失败的jar包maven是一款非常优秀的项目管理工具,特别是其
- 前情提要:本demo是基于springboot+mybatis-plus实现加密,加密为主,全局异常处理,日志处理为辅,而登录密码加密是每个
- 第1部分 TreeSet介绍TreeSet简介TreeSet 是一个有序的集合,它的作用是提供有序的Set集合。它继承于AbstractSe
- 1.设置url-pattern为*.do(最为常见的方式)只要你的请求url中包含配置的url-pattern,该url就可以到达Dispa
- 概述要想了解会话跟踪技术,我想我们要先了解一下会话是什么,以及会话跟踪技术存在的意义。首先我们要说的是:会话。会话 :见名知意,在现实中我们
- 本文实例为大家分享了java实现时间与字符串之间转换的具体代码,供大家参考,具体内容如下1. long字符串转换成yyyy-MM-dd HH
- IO流Java中IO流分为两种,字节流和字符流,顾名思义字节流就是按照字节来读取和写入的,字符刘是按照字符来存取的;常用的文件读取用的就是字
- java 中遍历取值异常(Hashtable Enumerator)解决办法用迭代器取值时抛出的异常:java.util.NoSuchEle
- 一、常见问题所有的final修饰的字段都是编译期常量吗?如何理解private所修饰的方法是隐式的final?说说final类型的类如何拓展
- 在一些项目的实际开发过程中,我们有时候需要对GridControl中列值进行转义,譬如1转义成“完成”等等,一般在诸如CustomColum
- 本文实例讲述了java内部类原理与用法。分享给大家供大家参考,具体如下:概念内部类:可以包含在另外一个类中的类外部类:包含内部类的类每个内部
- 本文实例为大家分享了C#语言实现ini文件读写操作的具体代码,供大家参考,具体内容如下1、ini文件是什么?见百度百科2、C#语言实现ini
- 概述在Java环境下创建定时任务有多种方式:使用while循环配合 Thread.sleep(),虽然稍嫌粗陋但也勉强可用使用 Timer和
- 本文实例为大家分享了Java手写线程池的实现代码,供大家参考,具体内容如下1.线程池是一种多线程处理形式,处理过程中将任务添加到队列,然后在
- 关于Android开发可以使用的工具有eclipse和Android studio等,这两个工具都各有各的好处和不足。studio是谷歌推出
- 1、前言当提及如何终止一个线程时,部分读者通常立马想到的方法肯定是stop(),但是stop()方法并不被推荐使用(很多规范中是禁止使用的)
- 说起双亲委派模型,不得不说一下类加载器。类加载器是什么?当我们编译Java类时,JVM会创建与平台和机器无关的字节码。字节码存储在.clas