当前位置: 首页 > 编程笔记 >

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

姚胡媚
2023-03-14
本文向大家介绍Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例,包括了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程序设计有所帮助。

 类似资料:
  • 本文向大家介绍PHP笛卡尔积实现算法示例,包括了PHP笛卡尔积实现算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了PHP笛卡尔积实现算法。分享给大家供大家参考,具体如下: 最终输出格式 Array (     [0] => 1,3,76     [1] => 1,3,6     [2] => 1,3,1     [3] => 1,3,0     [4] => 1,5,76    

  • 本文向大家介绍javascript笛卡尔积算法实现方法,包括了javascript笛卡尔积算法实现方法的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了javascript笛卡尔积算法实现方法。分享给大家供大家参考。具体分析如下: 这里可根据给的对象或者数组生成笛卡尔积 希望本文所述对大家的javascript程序设计有所帮助。

  • 现在我只能实现两个集合的笛卡尔积,下面是代码: 这段代码在IntelliJ中运行良好,但在Eclipse(两者的编译器遵从级别均为1.8)中就不行了: 下面是pair.java: 如何修复这个错误? 有没有一个优雅的方法来实现几个收藏的笛卡尔产品?(假设我们有类)

  • 本文向大家介绍PHP实现笛卡尔积算法的实例讲解,包括了PHP实现笛卡尔积算法的实例讲解的使用技巧和注意事项,需要的朋友参考一下 概念 在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为 X × Y。设A、B是任意两个集合,在集合A中任意取一个元素x,在集合B中任意取一个元素y,组成一个有序对(x,y),把这样的有序对作为新的元素,他们的全体组成的集合称为集合

  • 问题内容: 你是否知道一些精巧的Java库,可让你制作两个(或更多)集合的笛卡尔积? 例如:我有三套。一个对象是Person类的对象,第二个对象是Gift的对象,第三个对象是GiftExtension的对象。 我想生成一个包含所有可能的三元组的集合。 集的数量可能会有所不同,因此我无法在嵌套的foreach循环中执行此操作。在某些情况下,我的应用程序需要制作Person-Gift对的乘积,有时是的

  • 本文向大家介绍map reduce实现笛卡尔乘积?相关面试题,主要包含被问及map reduce实现笛卡尔乘积?时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 在Map阶段,将来自矩阵A的元素标识成l条<key,value>的形式,key=(i,k),k=1,2,…,l。value=(j,)。将来自矩阵B的元素标识成l条<key,value>的形式,key=(i,k),k=1,2,…,m。