当前访客身份:游客 [ 登录  | 注册加入尚学堂]
启用新域名sxt.cn
新闻资讯

笛卡尔乘积及java算法实现

helloworld 发表于 2年前  | 评论(0 )| 阅读次数(1328 )|   1 人收藏此文章,   我要收藏
在数学中,两个集合 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实现:

点击(此处)折叠或打开

    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<string>,多个集合构成List<List<string>> dimvalue作为输入
(2)将多维笛卡尔乘积的结果放到List<string> result之中作为输出
(3)int layer, string curstring只是两个中间过程的参数携带变量
(4)程序采用递归调用,起始调用示例如下:
分享到:0
关注微信,跟着我们扩展技术视野。每天推送IT新技术文章,每周聚焦一门新技术。微信二维码如下:
微信公众账号:尚学堂(微信号:bjsxt-java)
声明:博客文章版权属于原创作者,受法律保护。如果侵犯了您的权利,请联系管理员,我们将及时删除!
(邮箱:webmaster#sxt.cn(#换为@))
北京总部地址:北京市海淀区西三旗桥东建材城西路85号神州科技园B座三层尚学堂 咨询电话:400-009-1906 010-56233821
Copyright 2007-2015 北京尚学堂科技有限公司 京ICP备13018289号-1 京公网安备11010802015183