任意数量集合的笛卡尔积

2022-01-17 00:00:00 set cartesian-product java

您知道一些简洁的 Java 库，它们可以让您制作两个(或更多)集合的笛卡尔积吗?

Do you know some neat Java libaries that allow you to make cartesian product of two (or more) sets?

例如:我有三套.一个是 Person 类的对象，第二个是 Gift 类的对象，第三个是 GiftExtension 类的对象.

For example: I have three sets. One with objects of class Person, second with objects of class Gift and third with objects of class GiftExtension.

我想生成一组包含所有可能的三元组 Person-Gift-GiftExtension.

I want to generate one set containing all possible triples Person-Gift-GiftExtension.

集合的数量可能会有所不同，因此我无法在嵌套的 foreach 循环中执行此操作.在某些情况下，我的应用程序需要制作 Person-Gift pair 的乘积，有时它是三重 Person-Gift-GiftExtension，有时甚至可能会设置 Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension 等.

The number of sets might vary so I cannot do this in nested foreach loop. Under some conditions my application needs to make a product of Person-Gift pair, sometimes it is triple Person-Gift-GiftExtension, sometimes there might even be sets Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension, etc.

推荐答案

删除了以前的两套解决方案.有关详细信息，请参阅编辑历史记录.

Previous solutions for two sets removed. See edit history for details.

这是一种对任意数量的集合递归执行的方法:

Here is a way to do it recursively for an arbitrary number of sets:

public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
    if (sets.length < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " +
                sets.length + ")");

    return _cartesianProduct(0, sets);
}

private static Set<Set<Object>> _cartesianProduct(int index, Set<?>... sets) {
    Set<Set<Object>> ret = new HashSet<Set<Object>>();
    if (index == sets.length) {
        ret.add(new HashSet<Object>());
    } else {
        for (Object obj : sets[index]) {
            for (Set<Object> set : _cartesianProduct(index+1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

请注意，不可能在返回的集合中保留任何泛型类型信息.如果您事先知道要获取多少个集合的乘积，则可以定义一个通用元组来保存这么多元素(例如 Triple)，但是有在 Java 中无法拥有任意数量的泛型参数.

Note that it is impossible to keep any generic type information with the returned sets. If you knew in advance how many sets you wanted to take the product of, you could define a generic tuple to hold that many elements (for instance Triple<A, B, C>), but there is no way to have an arbitrary number of generic parameters in Java.

相关文章