Java中任意集的笛卡尔积

Question

您是否知道一些简洁的Java库,允许您制作两个(或更多)集的笛卡尔积？

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

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

集的数量可能会有所不同,所以我不能在嵌套的foreach循环中执行此操作.在某些情况下,我的应用程序需要制作一个Person-Gift对的产品,有时它是三人Person-Gift-GiftExtension,有时甚至可能会设置Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension等.

Answer 1

编辑:删除了两组的先前解决方案.有关详情,请参阅编辑历史

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

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<A, B, C>),但是没有办法在Java中拥有任意数量的泛型参数.

Answer 2

这是一个非常古老的问题,但为什么不使用Guava的cartesianProduct？

Answer 3

下面的方法创建一个字符串列表列表的笛卡尔积:

protected <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
    List<List<T>> resultLists = new ArrayList<List<T>>();
    if (lists.size() == 0) {
        resultLists.add(new ArrayList<T>());
        return resultLists;
    } else {
        List<T> firstList = lists.get(0);
        List<List<T>> remainingLists = cartesianProduct(lists.subList(1, lists.size()));
        for (T condition : firstList) {
            for (List<T> remainingList : remainingLists) {
                ArrayList<T> resultList = new ArrayList<T>();
                resultList.add(condition);
                resultList.addAll(remainingList);
                resultLists.add(resultList);
            }
        }
    }
    return resultLists;
}

例:

System.out.println(cartesianProduct(Arrays.asList(Arrays.asList("Apple", "Banana"), Arrays.asList("Red", "Green", "Blue"))));

会产生这个:

[[Apple, Red], [Apple, Green], [Apple, Blue], [Banana, Red], [Banana, Green], [Banana, Blue]]

Answer 4

集的数量可能会有所不同,所以我不能在嵌套的foreach循环中执行此操作.

两个提示:

• A x B x C = A x(B x C)
• 递归

Answer 5

基于索引的解决方案

使用索引是一种快速且具有内存效率的替代方案,可以处理任意数量的集合.实现Iterable允许在for-each循环中轻松使用.有关用法示例,请参阅#main方法.

public class CartesianProduct implements Iterable<int[]>, Iterator<int[]> {

    private final int[] _lengths;
    private final int[] _indices;
    private boolean _hasNext = true;

    public CartesianProduct(int[] lengths) {
        _lengths = lengths;
        _indices = new int[lengths.length];
    }

    public boolean hasNext() {
        return _hasNext;
    }

    public int[] next() {
        int[] result = Arrays.copyOf(_indices, _indices.length);
        for (int i = _indices.length - 1; i >= 0; i--) {
            if (_indices[i] == _lengths[i] - 1) {
                _indices[i] = 0;
                if (i == 0) {
                    _hasNext = false;
                }
            } else {
                _indices[i]++;
                break;
            }
        }
        return result;
    }

    public Iterator<int[]> iterator() {
        return this;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Usage example. Prints out
     * 
     * <pre>
     * [0, 0, 0] a, NANOSECONDS, 1
     * [0, 0, 1] a, NANOSECONDS, 2
     * [0, 0, 2] a, NANOSECONDS, 3
     * [0, 0, 3] a, NANOSECONDS, 4
     * [0, 1, 0] a, MICROSECONDS, 1
     * [0, 1, 1] a, MICROSECONDS, 2
     * [0, 1, 2] a, MICROSECONDS, 3
     * [0, 1, 3] a, MICROSECONDS, 4
     * [0, 2, 0] a, MILLISECONDS, 1
     * [0, 2, 1] a, MILLISECONDS, 2
     * [0, 2, 2] a, MILLISECONDS, 3
     * [0, 2, 3] a, MILLISECONDS, 4
     * [0, 3, 0] a, SECONDS, 1
     * [0, 3, 1] a, SECONDS, 2
     * [0, 3, 2] a, SECONDS, 3
     * [0, 3, 3] a, SECONDS, 4
     * [0, 4, 0] a, MINUTES, 1
     * [0, 4, 1] a, MINUTES, 2
     * ...
     * </pre>
     */
    public static void main(String[] args) {
        String[] list1 = { "a", "b", "c", };
        TimeUnit[] list2 = TimeUnit.values();
        int[] list3 = new int[] { 1, 2, 3, 4 };

        int[] lengths = new int[] { list1.length, list2.length, list3.length };
        for (int[] indices : new CartesianProduct(lengths)) {
            System.out.println(Arrays.toString(indices) //
                    + " " + list1[indices[0]] //
                    + ", " + list2[indices[1]] //
                    + ", " + list3[indices[2]]);
        }
    }
}