Chinaunix首页 | 论坛 | 博客
  • 博客访问: 6321146
  • 博文数量: 2759
  • 博客积分: 1021
  • 博客等级: 中士
  • 技术积分: 4091
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-11 14:14
文章分类

全部博文(2759)

文章存档

2019年(1)

2017年(84)

2016年(196)

2015年(204)

2014年(636)

2013年(1176)

2012年(463)

分类: Java

2014-08-12 10:07:24

在中,两个XY笛卡儿积(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)}。

java实现:

点击(此处)折叠或打开

  1. import java.util.ArrayList;
  2. import java.util.List;

  3. public class Descartes
  4. {

  5.     public static void run(List<List<String>> dimvalue, List<String> result, int layer, String curstring)
  6.     {
  7.         //大于一个集合时:
  8.         if (layer < dimvalue.size() - 1)
  9.         {
  10.             //大于一个集合时,第一个集合为空
  11.             if (dimvalue.get(layer).size() == 0)
  12.                 run(dimvalue, result, layer + 1, curstring);
  13.             else
  14.             {
  15.                 for (int i = 0; i < dimvalue.get(layer).size(); i++)
  16.                 {
  17.                     StringBuilder s1 = new StringBuilder();
  18.                     s1.append(curstring);
  19.                     s1.append(dimvalue.get(layer).get(i));
  20.                     run(dimvalue, result, layer + 1, s1.toString());
  21.                 }
  22.             }
  23.         }
  24.         //只有一个集合时:
  25.         else if (layer == dimvalue.size() - 1)
  26.         {
  27.             //只有一个集合,且集合中没有元素
  28.             if (dimvalue.get(layer).size() == 0)
  29.                 result.add(curstring);
  30.             //只有一个集合,且集合中有元素时:其笛卡尔积就是这个集合元素本身
  31.             else
  32.             {
  33.                 for (int i = 0; i < dimvalue.get(layer).size(); i++)
  34.                 {
  35.                     result.add(curstring + dimvalue.get(layer).get(i));
  36.                 }
  37.             }
  38.         }
  39.     }

  40.     
  41.     /**
  42.      * @param args
  43.      */
  44.     public static void main(String[] args)
  45.     {
  46.         List<List<String>> dimvalue = new ArrayList<List<String>>();
  47.         List<String> v1 = new ArrayList<String>();
  48.         v1.add("a");
  49.         v1.add("b");
  50.         List<String> v2 = new ArrayList<String>();
  51.         v2.add("c");
  52.         v2.add("d");
  53.         v2.add("e");
  54.         List<String> v3 = new ArrayList<String>();
  55.         v3.add("f");
  56.         v3.add("g");
  57.         
  58.         dimvalue.add(v1);
  59.         dimvalue.add(v2);
  60.         dimvalue.add(v3);
  61.         
  62.         List<String> result = new ArrayList<String>();
  63.         
  64.         Descartes.run(dimvalue, result, 0, "");
  65.         
  66.         int i = 1;
  67.         for (String s : result)
  68.         {
  69.             System.out.println(i++ + ":" +s);
  70.         }
  71.     }

  72. }
输出结果:


点击(此处)折叠或打开

  1. 1:acf
  2. 2:acg
  3. 3:adf
  4. 4:adg
  5. 5:aef
  6. 6:aeg
  7. 7:bcf
  8. 8:bcg
  9. 9:bdf
  10. 10:bdg
  11. 11:bef
  12. 12:beg
程序使用说明
(1)将每个维度的集合的元素视为List,多个集合构成List> dimvalue作为输入
(2)将多维笛卡尔乘积的结果放到List result之中作为输出
(3)int layer, string curstring只是两个中间过程的参数携带变量
(4)程序采用递归调用,起始调用示例如下:

阅读(816) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~