Java中笛卡尔的实现

这里介绍一种将多个数据元素拼成新的笛卡尔数据。

进行笛卡尔排序前的数据为:[a,b],[c],[d,e]，在进行笛卡尔算法处理之后的数据为：[a,c,d],[a,c,e],[b,c,d],[b,c,e]，一共四组结果。

实现基本思路：

1. 依次遍历每一组数据，首先将已经生成的集合按照当前遍历数据的长度扩展相应倍数；
2. 然后将当前遍历对象一次分配找已经生成的序列中；
3. 如此直至遍历结束，便可实现笛卡尔效果。

[a,b]
[c]
[d,e]

# 第一步
item1 = [a]
item2 = [b]

# 第二步，因为第二个数组只有一个长度，所以并不需要扩容
item1 = [a,c]
item2 = [b,c]

# 第三步，扩容两倍
item1 = [a,c]
item2 = [b,c]
item3 = [a,c]
item4 = [b,c]

# 第五步，将第三个数据平均分配到数列中
item1 = [a,c,d]
item2 = [b,c,d]
item3 = [a,c,e]
item4 = [b,c,e]

按照上面的步骤就是一个很简单的笛卡尔算法的实现。

具体JAVA的实现过程中，需要注意以下几点：

1. 集合的深度复制，不能用addAll(Collection)；

具体的代码实现如下：

package com.songwh.kalisee.utils;

import org.springframework.util.CollectionUtils;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class TestDikaer {

    public static void main(String[] args) {
        List<String[]> list = new ArrayList<>();
        list.add(new String[]{"a"});
        list.add(new String[]{"c", "d","z"});
        list.add(new String[]{"e",});
        list.add(new String[]{"f", "g"});
        List<List<String>> resultList = new ArrayList<>();
        dicaer(list, resultList);
        for (List<String> strings : resultList) {
            System.out.println(strings);
        }
    }

    private static void dicaer(List<String[]> list, List<List<String>> resultList) {
        for (String[] strings : list) {
            int length = strings.length;
            // 如果是第一次则直接将将数据拆分进来即可
            if (CollectionUtils.isEmpty(resultList)) {
                for (String string : strings) {
                    List<String> tempList = new ArrayList<>();
                    tempList.add(string);
                    resultList.add(tempList);
                }
                continue;
            }
            // 如果不是第一次则需要将列表翻倍
            serlCopy(resultList, length - 1);
            int size = resultList.size();
            // 将数组中的数据平均分配到集合中
            for (int i = 0; i < size; i++) {
                resultList.get(i).add(strings[i / (size / length)]);
            }
        }
    }

    private static void serlCopy(List<List<String>> resultList, int length) {
        List<List<String>> clone = (List) clone(resultList);
        for (int i = 0; i < length; i++) {
            List<List<String>> clone2 = (List) clone(clone);
            resultList.addAll(clone2);
        }
    }

    /**
     * 深度复制对象
     * @param obj
     * @param <T>
     * @return
     */
    public static <T extends Serializable> T clone(List<List<String>> obj) {
        T cloneObj = null;
        try {
            //写入字节流
            ByteArrayOutputStream out = new ByteArrayOutputStream();
            ObjectOutputStream obs = new ObjectOutputStream(out);
            obs.writeObject(obj);
            obs.close();
            //分配内存，写入原始对象，生成新对象
            ByteArrayInputStream ios = new ByteArrayInputStream(out.toByteArray());
            ObjectInputStream ois = new ObjectInputStream(ios);
            //返回生成的新对象
            cloneObj = (T) ois.readObject();
            ois.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return cloneObj;
    }
}

运行结果：