笛卡尔乘积及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)}。

java实现：

import java.util.ArrayList;
import java.util.List;

public class Descartes
{

    public static void run(List<List<String>> dimvalue, List<String> result, int layer, String curstring)
    {
        //大于一个集合时：
        if (layer < dimvalue.size() - 1)
        {
            //大于一个集合时，第一个集合为空
            if (dimvalue.get(layer).size() == 0)
                run(dimvalue, result, layer + 1, curstring);
            else
            {
                for (int i = 0; i < dimvalue.get(layer).size(); i++)
                {
                    StringBuilder s1 = new StringBuilder();
                    s1.append(curstring);
                    s1.append(dimvalue.get(layer).get(i));
                    run(dimvalue, result, layer + 1, s1.toString());
                }
            }
        }
        //只有一个集合时：
        else if (layer == dimvalue.size() - 1)
        {
            //只有一个集合，且集合中没有元素
            if (dimvalue.get(layer).size() == 0)
                result.add(curstring);
            //只有一个集合，且集合中有元素时：其笛卡尔积就是这个集合元素本身
            else
            {
                for (int i = 0; i < dimvalue.get(layer).size(); i++)
                {
                    result.add(curstring + dimvalue.get(layer).get(i));
                }
            }
        }
    }


    /**
     * @param args
     */
    public static void main(String[] args)
    {
        List<List<String>> dimvalue = new ArrayList<List<String>>();
        List<String> v1 = new ArrayList<String>();
        v1.add("a");
        v1.add("b");
        List<String> v2 = new ArrayList<String>();
        v2.add("c");
        v2.add("d");
        v2.add("e");
        List<String> v3 = new ArrayList<String>();
        v3.add("f");
        v3.add("g");

        dimvalue.add(v1);
        dimvalue.add(v2);
        dimvalue.add(v3);

        List<String> result = new ArrayList<String>();

        Descartes.run(dimvalue, result, 0, "");

        int i = 1;
        for (String s : result)
        {
            System.out.println(i++ + ":" +s);
        }
    }

}

输出结果：

1:acf
2:acg
3:adf
4:adg
5:aef
6:aeg
7:bcf
8:bcg
9:bdf
10:bdg
11:bef
12:beg

程序使用说明

（1）将每个维度的集合的元素视为List,多个集合构成List> dimvalue作为输入

（2）将多维笛卡尔乘积的结果放到List result之中作为输出

（3）int layer, string curstring只是两个中间过程的参数携带变量

（4）程序采用递归调用，起始调用示例如下：