Java多维数组递归，无论数组大小

Question

我有三个数组：

{}    
{a, b, c}
{d, e} 

我正在尝试将它们组合以获得以下数组：

{a, d}
{a, e}
{b, d}
{b, e}
{c, d} 
{c, e}

我遇到的问题是第一个空数组导致嵌套的for循环根本不运行 - 这在逻辑上是有道理的。例如:

 for (int i = 0; i < bL.size(); i++) {
        for (int j = 0; j < dL.size(); j++) {
            for (int k = 0; k < oL.size(); k++) {

我试图找到一种最有效的方法来合并这三个数组，而不考虑它们的大小。大多数情况下，这三个数组都有元素，但也有可能其中一个为空集。

任何帮助都将不胜感激。

编辑：添加所有三个数组的输出

输入- {a,b} {c,d} {e,f}

输出- {a,c,e} {a,c,f} {a,d,e} {a,d,f} {b,c,e} {b,c,f}

编辑：只有第一个或第三个数组可能为空集。

- Josh

---

为什么不直接递归调用一个合并两个数组的方法，在该方法内处理空数组的特殊情况？你甚至不需要递归调用，只需先将前两个数组合并，然后再将当前组合结果和下一个数组一起调用该方法。 - Thomas

假设第一个数组有元素{f,g}，在这种情况下应该是什么答案？ - President James K. Polk

@GregS 我认为他想要一个笛卡尔积，尽管它的不同之处在于空数组/集合实际上被忽略了。 - Thomas

@Thomas 我能理解这种方法的工作原理。这是否被认为是实现笛卡尔积的常见做法？ - Josh

@Josh 生成潜在无限集的笛卡尔积并不太常见，因为存在消耗大量内存的风险。通常，您还希望根据某些标准过滤结果，并将这两个操作合并为一个操作。但如果内存消耗不是问题，并且您不能立即减少结果的大小，则可以继续进行该操作。 - biziclop

Answer 1

假设你正在处理 int 值的数组，这里是你可以做的事情：

void printCombination(int[][] data, List<int> partial) {
    if (partial.size() == data.Length) {
        for (int i : partial) {
            if (i != -1) {
                System.out.writeln(" " + i);
            }
        }
        return;
    }
    if (data[partial.size()].length == 0) {
        partial.add(-1);
        printCombination(data, partial);
        partial.remove(partial.size()-1);
        return;
    }
    for (int i = 0 ; i != data[partial.size()].length; i++) {
        partial.add(data[partial.size()][i]);
        printCombination(data, partial);
        partial.remove(partial.size()-1);
    }
}

初始调用看起来像这样：

List<int> partial = new ArrayList();
int[][] data = new int[][] {new int[] {}, new int[] {1,2}, new int[] {3, 4, 5}};
printCombination(data, partial);

- Sergey Kalinichenko

---

“p”和“str”是从哪里来的？我试图跟着逻辑走。实际上，我正在使用Character[]。 - Josh

当尝试访问空数组时，partial.add(data[partial.size()][i]);这行代码会产生ArrayIndexOutOfBounds异常，不是吗？ - Josh

此外，看起来这个逻辑会创建一个包含每个数组中所有元素的单一列表，而不是多个包含每个数组中单个元素所有可能组合的数组。 - Josh

@Josh 不会有任何异常，但是代码不会按预期运行，因为循环将不会执行任何次数。您需要稍微修改一下以支持空数组（请参见我的编辑）。 - Sergey Kalinichenko

@dasblinkenlight 那输出不是仍然会是 {1,2,3,4,5} 而不是 {1,3}{1,4}{1,5}{2,3}{2,4}{2,5} 吗？ - Josh

Answer 2

这里有一个简单的递归方法，它将结果作为2D ArrayList返回而不是打印出来。

import java.util.ArrayList;

public class Program
{
    public static void main(String[] args)
    {
        String[][] x = { {}, {"a", "b", "c"}, {"d", "e"} };
        System.out.println(cartProd(x));
    }

    public static ArrayList< ArrayList<String> > cartProd(String[][] x)
    {
        return cartProd(x, new ArrayList<String>(), 0);
    }

    public static ArrayList< ArrayList<String> > cartProd(String[][] x, ArrayList<String> current, int index)
    {
        ArrayList< ArrayList<String> > result = new ArrayList< ArrayList<String> >();

        while (index < x.length && x[index].length == 0)
        {
            index++;
        }

        if (index == x.length)
        {
            result.add(new ArrayList<String>(current));
        }
        else
        {
            for (int i = 0; i < x[index].length; i++)
            {
                current.add(x[index][i]);
                result.addAll(cartProd(x, current, index + 1));
                current.remove(current.size() - 1);
            }
        }

        return result;
    }
}

- tom