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)}。

如何用程序算法实现笛卡尔积?

如果编程前已知集合的数量,通过程序的多次循环即可得出笛卡尔积。但是如果编程前不知道集合的数量,如何得到笛卡尔积哪?比如集合表示List < List<String>> list;这个list在编程前list的数量是未知的。下面的代码使用递归和循环两种方法实现未知维度集合的笛卡尔积:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * 循环和递归两种方式实现未知维度集合的笛卡尔积
 * Created on 2015-05-22
 * @author luweijie
 */
public class Descartes {
  /**
   * 递归实现dimValue中的笛卡尔积,结果放在result中
   * @param dimValue 原始数据
   * @param result 结果数据
   * @param layer dimValue的层数
   * @param curList 每次笛卡尔积的结果
   */
  private static void recursive (List<List<String>> dimValue, List<List<String>> result, int layer, List<String> curList) {
    if (layer < dimValue.size() - 1) {
      if (dimValue.get(layer).size() == 0) {
        recursive(dimValue, result, layer + 1, curList);
      } else {
        for (int i = 0; i < dimValue.get(layer).size(); i++) {
          List<String> list = new ArrayList<String>(curList);
          list.add(dimValue.get(layer).get(i));
          recursive(dimValue, result, layer + 1, list);
        }
      }
    } else if (layer == dimValue.size() - 1) {
      if (dimValue.get(layer).size() == 0) {
        result.add(curList);
      } else {
        for (int i = 0; i < dimValue.get(layer).size(); i++) {
          List<String> list = new ArrayList<String>(curList);
          list.add(dimValue.get(layer).get(i));
          result.add(list);
        }
      }
    }
  }
  /**
   * 循环实现dimValue中的笛卡尔积,结果放在result中
   * @param dimValue 原始数据
   * @param result 结果数据
   */
  private static void circulate (List<List<String>> dimValue, List<List<String>> result) {
    int total = 1;
    for (List<String> list : dimValue) {
      total *= list.size();
    }
    String[] myResult = new String[total];
    int itemLoopNum = 1;
    int loopPerItem = 1;
    int now = 1;
    for (List<String> list : dimValue) {
      now *= list.size();
      int index = 0;
      int currentSize = list.size();
      itemLoopNum = total / now;
      loopPerItem = total / (itemLoopNum * currentSize);
      int myIndex = 0;
      for (String string : list) {
        for (int i = 0; i < loopPerItem; i++) {
          if (myIndex == list.size()) {
            myIndex = 0;
          }
          for (int j = 0; j < itemLoopNum; j++) {
            myResult[index] = (myResult[index] == null? "" : myResult[index] + ",") + list.get(myIndex);
            index++;
          }
          myIndex++;
        }
      }
    }
    List<String> stringResult = Arrays.asList(myResult);
    for (String string : stringResult) {
      String[] stringArray = string.split(",");
      result.add(Arrays.asList(stringArray));
    }
  }
  /**
   * 程序入口
   * @param args
   */
  public static void main (String[] args) {
    List<String> list1 = new ArrayList<String>();
    list1.add("1");
    list1.add("2");
    List<String> list2 = new ArrayList<String>();
    list2.add("a");
    list2.add("b");
    List<String> list3 = new ArrayList<String>();
    list3.add("3");
    list3.add("4");
    list3.add("5");
    List<String> list4 = new ArrayList<String>();
    list4.add("c");
    list4.add("d");
    list4.add("e");
    List<List<String>> dimValue = new ArrayList<List<String>>();
    dimValue.add(list1);
    dimValue.add(list2);
    dimValue.add(list3);
    dimValue.add(list4);
    List<List<String>> recursiveResult = new ArrayList<List<String>>();
    // 递归实现笛卡尔积
    recursive(dimValue, recursiveResult, 0, new ArrayList<String>());
    System.out.println("递归实现笛卡尔乘积: 共 " + recursiveResult.size() + " 个结果");
    for (List<String> list : recursiveResult) {
      for (String string : list) {
        System.out.print(string + " ");
      }
      System.out.println();
    }
    List<List<String>> circulateResult = new ArrayList<List<String>>();
    circulate(dimValue, circulateResult);
    System.out.println("循环实现笛卡尔乘积: 共 " + circulateResult.size() + " 个结果");
    for (List<String> list : circulateResult) {
      for (String string : list) {
        System.out.print(string + " ");
      }
      System.out.println();
    }
  }
}

输出结果是:

递归实现笛卡尔乘积: 共 36 个结果
1 a 3 c
1 a 3 d
1 a 3 e
1 a 4 c
1 a 4 d
1 a 4 e
1 a 5 c
1 a 5 d
1 a 5 e
1 b 3 c
1 b 3 d
1 b 3 e
1 b 4 c
1 b 4 d
1 b 4 e
1 b 5 c
1 b 5 d
1 b 5 e
2 a 3 c
2 a 3 d
2 a 3 e
2 a 4 c
2 a 4 d
2 a 4 e
2 a 5 c
2 a 5 d
2 a 5 e
2 b 3 c
2 b 3 d
2 b 3 e
2 b 4 c
2 b 4 d
2 b 4 e
2 b 5 c
2 b 5 d
2 b 5 e
循环实现笛卡尔乘积: 共 36 个结果
1 a 3 c
1 a 3 d
1 a 3 e
1 a 4 c
1 a 4 d
1 a 4 e
1 a 5 c
1 a 5 d
1 a 5 e
1 b 3 c
1 b 3 d
1 b 3 e
1 b 4 c
1 b 4 d
1 b 4 e
1 b 5 c
1 b 5 d
1 b 5 e
2 a 3 c
2 a 3 d
2 a 3 e
2 a 4 c
2 a 4 d
2 a 4 e
2 a 5 c
2 a 5 d
2 a 5 e
2 b 3 c
2 b 3 d
2 b 3 e
2 b 4 c
2 b 4 d
2 b 4 e
2 b 5 c
2 b 5 d
2 b 5 e

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

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

(0)

相关推荐

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

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

  • Java实现DFA算法对敏感词、广告词过滤功能示例

    一.前言 开发中经常要处理用户一些文字的提交,所以涉及到了敏感词过滤的功能,参考资料中DFA有穷状态机算法的实现,创建有向图.完成了对敏感词.广告词的过滤,而且效率较好,所以分享一下. 具体实现: 1.匹配大小写过滤  2.匹配全角半角过滤  3.匹配过滤停顿词过滤.  4.敏感词重复词过滤. 例如: 支持如下类型类型过滤检测: fuck 全小写 FuCk 大小写 fuck全角半角 f!!!u&c ###k 停顿词 fffuuuucccckkk 重复词 敏感词过滤的做法有很多,我简单描述我现在理

  • 关于JAVA经典算法40题(超实用版)

    [程序1]题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第四个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?1.程序分析: 兔子的规律为数列1,1,2,3,5,8,13,21....public class exp2{ public static void main(String args[]){ int i=0; for(i=1;i<=20;i++)System.out.println(f(i));}public static int f(in

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

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

  • Java矩阵连乘问题(动态规划)算法实例分析

    本文实例讲述了Java矩阵连乘问题(动态规划)算法.分享给大家供大家参考,具体如下: 问题描述:给定n个矩阵:A1,A2,...,An,其中Ai与Ai+1是可乘的,i=1,2...,n-1.确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少.输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数. 问题解析:由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序.这种计算次序可以用加括号的方式来确定.若一个矩阵连乘积的计算次序完全确

  • Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

    本文实例讲述了Java基于栈方式解决汉诺塔问题.分享给大家供大家参考,具体如下: /** * 栈方式非递归汉诺塔 * @author zy * */ public class StackHanoi { /** * @param args */ public static void main(String[] args) { System.out.println("我们测试结果:"); System.out.println("递归方式:"); hanoiNormal(

  • Java编程实现A*算法完整代码

    前言 A*搜寻算法俗称A星算法.这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法.常用于游戏中 通过二维数组构建的一个迷宫,"%"表示墙壁,A为起点,B为终点,"#"代表障碍物,"*"代表算法计算后的路径 本文实例代码结构: % % % % % % % % o o o o o % % o o # o o % % A o # o B % % o o # o o % % o o o o o % % % % % % % % =======

  • 基于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.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

  • Java基于分治算法实现的棋盘覆盖问题示例

    本文实例讲述了Java基于分治算法实现的棋盘覆盖问题.分享给大家供大家参考,具体如下: 在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖.四个L型骨牌如下图: 棋盘中的特殊方格如图: 实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不

  • Java语言实现Blowfish加密算法完整代码分享

    前几天网上突然出现流言:某东发生数据泄露12G,最终某东在一篇声明中没有否认,还算是勉强承认了吧,这件事对于一般人有什么影响.应该怎么做已经有一堆人说了,所以就不凑热闹了,咱来点对程序猿来说实际点的,说一个个人认为目前比较安全的加密算法:Blowfish. 上代码之前,先说几点Blowfish加密算法的特点: 1. 对称加密,即加密的密钥和解密的密钥是相同的: 2. 每次加密之后的结果是不同的(这也是老夫比较欣赏的一点): 3. 可逆的,和老夫之前的文章介绍的md5等摘要算法不一样,他是可逆的:

随机推荐