时间戳

首页 > 解决方案 > ArrayLists笛卡尔积元素的正确顺序

java - ArrayLists笛卡尔积元素的正确顺序

问题描述

我试图根据这个答案生成未知数量的 ArrayLists（固定类型）的笛卡尔积：任意数量的集合的笛卡尔积。但是我发现了一些奇怪的东西。笛卡尔积总是以相反的顺序给出。例如，如果 A 和 B 是两个 List，则在笛卡尔对中首先给出 B 的元素，然后给出 A 的元素。可能的原因是什么？如何解决？原始回答者说，在笛卡尔积中订购无关紧要。但我认为在制作笛卡尔产品时订购是主要的事情，尤其是当每组代表平面坐标时。

修改代码：

private static Set<ArrayList<Double>> cartesianProduct(ArrayList<ArrayList<Double>> sets) {
    if (sets.size() < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " +
                        sets.size() + ")");

    return _cartesianProduct(0, sets);
}

private static Set<ArrayList<Double>> _cartesianProduct(int index, ArrayList<ArrayList<Double>> sets) {
    Set<ArrayList<Double>> ret = new HashSet<>();
    if (index == sets.size()) {
        ret.add(new ArrayList<>());
    } else {
        for (Double obj : sets.get(index)) {
            for (ArrayList<Double> set : _cartesianProduct(index + 1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

输出：

ArrayList<Double> l1 = new ArrayList<>(Arrays.asList(1.0, 2.0));
ArrayList<Double> l2 = new ArrayList<>(Arrays.asList(4.0, 5.0));
ArrayList<ArrayList<Double>> l = new ArrayList<>(Arrays.asList(l1, l2));
Set<ArrayList<Double>> a = cartesianProduct(l);

// a = [[4.0, 1.0], [4.0, 2.0], [5.0, 1.0], [5.0, 2.0]]

标签： javaarraylistcartesian-product

解决方案

这是因为递归。索引最初为 0，因此在第 1 行for (ArrayList<Double> set : _cartesianProduct(index + 1, sets)) {，您的代码再次调用cartesianProductindex=1。它再次到达那条线，并cartesianProduct以 index=2 调用。当它位于 index=2 时，它会达到其基本情况并返回一个带有空的集合ArrayList。

然后它返回到 index=1 的堆栈帧（请记住，obj是 4.0，因为sets.get(1)ArrayList 包含 4 和 6）。它将所有双精度sets.get(index)（这里是 4.0 和 6.0）添加到它们自己的 ArrayLists 中ret。然后它到达 foreach 循环的末尾并返回集合，该集合现在有 2 个 ArrayList，一个包含 4.0，另一个包含 6.0。

在 index=0 时也是如此，因此第一个列表（或集合）的元素添加在第二个列表的元素之后。这就是为什么你会得到相反的结果。

要解决此问题，您可以每次减少索引，从 sets.size() 变为 0 而不是相反。要反转它，您也可以简单地在结果中的每个集合上调用 Collections.reverse()。

//Fix by decrementing index
private static Set<ArrayList<Double>> cartesianProduct(ArrayList<ArrayList<Double>> sets) {
    if (sets.size() < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " + sets.size() + ")");
    //Be sure to start at the end of 'sets' so you can go down by one
    return cartesianProduct(sets.size() - 1, sets);
}

private static Set<ArrayList<Double>> cartesianProduct(int index, ArrayList<ArrayList<Double>> sets) {
    Set<ArrayList<Double>> ret = new HashSet<>();
    //Counting to 0 instead of to the end of the sets ArrayList
    if (index < 0) {
        ret.add(new ArrayList<>());
    } else {
        for (Double obj : sets.get(index)) {
            for (ArrayList<Double> set : cartesianProduct(index - 1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

//Alternative answer using Collections.reverse
private static Set<ArrayList<Double>> cartesianProduct(ArrayList<ArrayList<Double>> sets) {
    if (sets.size() < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " + sets.size() + ")");
    //This basically goes through the set of sets and reverses each ArrayList
    return cartesianProduct(0, sets).stream().map(Collections::reverse).collect(Collectors.toSet());
}

推荐阅读