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<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算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

(0)

相关推荐

  • Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例

    本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积.分享给大家供大家参考,具体如下: 什么是笛卡尔积? 在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员. 假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}. 如何用程序算法实现笛卡尔积? 如果编程前已知集合的数量

  • K均值聚类算法的Java版实现代码示例

    1.简介 K均值聚类算法是先随机选取K个对象作为初始的聚类中心.然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心.聚类中心以及分配给它们的对象就代表一个聚类.一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算.这个过程将不断重复直到满足某个终止条件.终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小. 2.什么是聚类 聚类是一个将数据集中在某些方面相似的数据成员进行分类组织

  • Java编程实现打印螺旋矩阵实例代码

    直接上代码吧. 昨晚腾讯在线测试遇到的题. 螺旋矩阵是指一个呈螺旋状的矩阵,它的数字由第一行开始到右边不断变大,向下变大,向左变大,向上变大,如此循环. import java.util.Scanner; public class mysnakematrix { private int n; // private int a[][]; // 声明一个矩阵 private int value = 1; // 矩阵里数字的值 public mysnakematrix(int i) { this.n

  • 70行Java代码实现深度神经网络算法分享

    对于现在流行的深度学习,保持学习精神是必要的--程序员尤其是架构师永远都要对核心技术和关键算法保持关注和敏感,必要时要动手写一写掌握下来,先不用关心什么时候用到--用不用是政治问题,会不会写是技术问题,就像军人不关心打不打的问题,而要关心如何打赢的问题. 程序员如何学习机器学习 对程序员来说,机器学习是有一定门槛的(这个门槛也是其核心竞争力),相信很多人在学习机器学习时都会为满是数学公式的英文论文而头疼,甚至可能知难而退.但实际上机器学习算法落地程序并不难写,下面是70行代码实现的反向多层(BP

  • 基于Java实现的一层简单人工神经网络算法示例

    本文实例讲述了基于Java实现的一层简单人工神经网络算法.分享给大家供大家参考,具体如下: 先来看看笔者绘制的算法图: 2.数据类 import java.util.Arrays; public class Data { double[] vector; int dimention; int type; public double[] getVector() { return vector; } public void setVector(double[] vector) { this.vect

  • Java分治归并排序算法实例详解

    本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,

  • Java编程实现基于用户的协同过滤推荐算法代码示例

    协同过滤简单来说是利用某兴趣相投.拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要. 协同过滤又可分为评比(rating)或者群体过滤(social filtering)协同过滤以其出色的速度和健壮性,在全球互联网领域炙手可热 UserCF的核心思想即为根据用户数据模拟向量相似度,我们根据这个相似度,来找出指定用户的相似用户,然后将相似用

  • Java语言实现快速幂取模算法详解

    快速幂取模算法的引入是从大数的小数取模的朴素算法的局限性所提出的,在朴素的方法中我们计算一个数比如5^1003%31是非常消耗我们的计算资源的,在整个计算过程中最麻烦的就是我们的5^1003这个过程 缺点1:在我们在之后计算指数的过程中,计算的数字不都拿得增大,非常的占用我们的计算资源(主要是时间,还有空间) 缺点2:我们计算的中间过程数字大的恐怖,我们现有的计算机是没有办法记录这么长的数据的,所以说我们必须要想一个更加高效的方法来解决这个问题 当我们计算AB%C的时候,最便捷的方法就是调用Ma

  • Java笛卡尔积算法原理与实现方法详解

    本文实例讲述了Java笛卡尔积算法原理与实现方法.分享给大家供大家参考,具体如下: 笛卡尔积算法的Java实现: (1)循环内,每次只有一列向下移一个单元格,就是CounterIndex指向的那列. (2)如果该列到尾部了,则这列index重置为0,而CounterIndex则指向前一列,相当于进位,把前列的index加一. (3)最后,由生成的行数来控制退出循环. public class Test { private static String[] aa = { "aa1", &q

  • Java贪心算法之Prime算法原理与实现方法详解

    本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在

  • java的继承原理与实现方法详解

    本文实例讲述了java的继承原理与实现方法.分享给大家供大家参考,具体如下: 继承 1.java中是单继承的.每个子类只有一个父类. 语法:子类 extends 父类 2.在java中,即使没有声明父类,也有一个隐含的父类,就是Object类 3.在子类中可以使用super来调用父类的方法 4.继承中的构造方法问题 在new一个子类实例的过程中,会优先自动调用父类默认的无参数构造方法,然后再调用子类的构造方法.如果父类没有默认的构造方法,只有带参数的构造方法,此时就会出错. 除了由jvm自动调用

  • JS前端面试必备——基本排序算法原理与实现方法详解【插入/选择/归并/冒泡/快速排序】

    本文实例讲述了JS前端面试必备--基本排序算法原理与实现方法.分享给大家供大家参考,具体如下: 排序算法是面试及笔试中必考点,本文通过动画方式演示,通过实例讲解,最后给出JavaScript版的排序算法 插入排序 算法描述: 1. 从第一个元素开始,该元素可以认为已经被排序 2. 取出下一个元素,在已经排序的元素序列中从后向前扫描 3. 如果该元素(已排序)大于新元素,将该元素移到下一位置 4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到该位置后 6. 重复

  • Go Java算法之比较版本号方法详解

    目录 比较版本号 方法一:字符串切割(Java) 方法二:双指针(Go) 比较版本号 给你两个版本号 version1 和 version2 ,请你比较它们. 版本号由一个或多个修订号组成,各修订号由一个 '.' 连接.每个修订号由 多位数字 组成,可能包含 前导零 .每个版本号至少包含一个字符. 修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推.例如,2.5.33 和 0.1 都是有效的版本号. 比较版本号时,请按从左到右的顺序依次比较它们的

  • ThreadPoolExecutor线程池原理及其execute方法(详解)

    jdk1.7.0_79 对于线程池大部分人可能会用,也知道为什么用.无非就是任务需要异步执行,再者就是线程需要统一管理起来.对于从线程池中获取线程,大部分人可能只知道,我现在需要一个线程来执行一个任务,那我就把任务丢到线程池里,线程池里有空闲的线程就执行,没有空闲的线程就等待.实际上对于线程池的执行原理远远不止这么简单. 在Java并发包中提供了线程池类--ThreadPoolExecutor,实际上更多的我们可能用到的是Executors工厂类为我们提供的线程池:newFixedThreadP

  • Java 数据结构算法Collection接口迭代器示例详解

    目录 Java合集框架 Collection接口 迭代器 Java合集框架 数据结构是以某种形式将数据组织在一起的合集(collection).数据结构不仅存储数据,还支持访问和处理数据的操作 在面向对象的思想里,一种数据结构也被认为是一个容器(container)或者容器对象(container object),它是一个能存储其他对象的对象,这里的其他对象常被称为数据或者元素 定义一种数据结构从实质上讲就是定义一个类.数据结构类应该使用数据域存储数据,并提供方法支持查找.插入和删除等操作 Ja

  • Java实现验证文件名有效性的方法详解

    目录 使用java.io.File 使用 NIO2 API 自定义的实现 使用String.contains 正则表达式模式匹配 总结 在本文中,我们将讨论使用 Java 验证一个给定的字符串是否具有操作系统的有效文件名的不同方法.我们可以根据限制的字符或长度限制来检查该值. 我们将只关注核心解决方案,不使用任何外部依赖.我们将使用JDK的java.io和NIO2包来实现我们验证方法.. 使用java.io.File 让我们从第一个例子开始,使用 java.io.File 类.在这个解决方案中,

  • Java的JSON处理器fastjson使用方法详解

    fastjson 是一个性能很好的 Java 语言实现的 JSON 解析器和生成器,来自阿里巴巴的工程师开发. 主要特点: • 快速FAST (比其它任何基于Java的解析器和生成器更快,包括jackson) • 强大(支持普通JDK类包括任意Java Bean Class.Collection.Map.Date或enum) • 零依赖(没有依赖其它任何类库除了JDK) 示例代码: import com.alibaba.fastjson.JSON; Group group = new Group

  • Java和C#输入输出流的方法(详解)

    1,Java中操作方法: import java.io.*; public class FileInputStreamTest { public static void main(String[] args) throws IOException { //创建字节输入流 FileInputStream fis = new FileInputStream("FileInputStreamTest.java"); //创建一个长度为1024的竹筒 byte[] bbuf = new byt

随机推荐