笛卡尔积工具类

guqing

2020-10-14

Java Tools

4296

在数学中，两个集合X和Y的笛卡儿积，又称直积，在集合论中表示为X x Y，是所有可能的有序对组成的集合，其中有序对的第一个对象是X的成员，第二个对象是Y的成员。

X×Y={(x,y)∣x∈X∧y∈Y}

举个实例,假设有两个集合 A 和 B:

A = {0,1}
B = {2,3,4}

那么A和B的笛卡尔积 A×B 表示如下：

A×B = {（0，2），（1，2），（0，3），（1，3），（0，4），（1，4）}

笛卡尔积的Java实现如下:

/**
 * 笛卡尔积工具类
 *
 * @author guqing
 * @date 2020-10-13
 */
public class CartesianUtils {
    public static<T> List<List<T>> cartesianProduct(List<List<T>> dimensionValue) {
        List<List<T>> result = new LinkedList<>();
        cartesianProduct(dimensionValue, result, 0, new ArrayList<>());
        return result;
    }

    private static<T> void cartesianProduct(List<List<T>> dimensionValue, List<List<T>> result, int layer, List<T> currentList) {
        if (layer < dimensionValue.size() - 1) {
            if (dimensionValue.get(layer).size() == 0) {
                cartesianProduct(dimensionValue, result, layer + 1, currentList);
            } else {
                for (int i = 0; i < dimensionValue.get(layer).size(); i++) {
                    List<T> list = new ArrayList<>(currentList);
                    list.add(dimensionValue.get(layer).get(i));
                    cartesianProduct(dimensionValue, result, layer + 1, list);
                }
            }
        } else if (layer == dimensionValue.size() - 1) {
            if (dimensionValue.get(layer).size() == 0) {
                result.add(currentList);
            } else {
                for (int i = 0; i < dimensionValue.get(layer).size(); i++) {
                    List<T> list = new ArrayList<>(currentList);
                    list.add(dimensionValue.get(layer).get(i));
                    result.add(list);
                }
            }
        }
    }
}