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的数量是未知的。下面的代码使用递归和循环两种方法实现未知维度集合的笛卡尔积：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

									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