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程序设计有所帮助。