java - 从两个排序数组的交替元素生成所有可能的排序数组

Question

我正在处理以下问题，并且不明白它是如何在遵循作为对 this question in stackoverflow 的答案提供的递归解决方案后获得所有结果数组的。 :

问题是:给定两个排序数组 A 和 B，生成所有可能的数组，使得第一个元素取自 A，然后取自 B，然后取自 A，依此类推，直到数组耗尽.生成的数组应以 B 中的元素结尾。

例子: A = {10, 15, 25} B = {1, 5, 20, 30}

结果数组是: [10 20] , [10 20 25 30], [10 30], [15 20], [15 20 25 30], [15 30], [25 30] 建议的解决方案:

public static void main(String[] args) {

    int[] A = {10, 15, 25};
    int[] B = {1, 5, 20, 30};

    Stack<Integer> st = new Stack<>();

    for (int i = 0; i < A.length; i++) {
        st.push(A[i]);
        generateArrays(A, B, i, 0, st, false);
        st.clear();
    }
}

static void generateArrays(int ar1[], int ar2[], int index_of_a, int index_of_b, Stack<Integer> st, boolean first) {
    if (index_of_a >= ar1.length || index_of_b >= ar2.length) {
        st.pop();
        return;
    }

    // take from second if available
    if (!first) {
        for (int j = index_of_b; j < ar2.length; j++) {
            if (ar1[index_of_a] < ar2[j]) {
                st.push(ar2[j]);
                System.out.println(st);
                generateArrays(ar1, ar2, index_of_a + 1, j, st, true);
            }
        }
    }

    // take from first if available
    else if (first) {
        for (int i = index_of_a; i < ar1.length; i++) {
            if (ar1[i] > ar2[index_of_b]) {
                st.push(ar1[i]);
                generateArrays(ar1, ar2, i, index_of_b + 1, st, false);
            }
        }
    }

    st.pop();
}

我自己用给定的输入示例手动执行算法后，结果数组中没有得到 [10 30]、[15 30]。

所以，我尝试通过调试代码来理解，发现index of a和index of b每次for i 或 j 上的循环以及 first 的值都不会继续进行，直到我们得到 a = 0 的索引和 b = 1 的索引。为什么会这样？我在算法执行流程中缺少什么？算法如何得到输出中的[10 30]、[15 30]？

Answer 1

请注意，每次调用 generateArrays() 都会弹出堆栈(堆栈是一个对象，因此在所有方法调用中都是相同的)并因此使其返回到其原始状态，因此您可以假设在每次迭代之后在 for 循环中，堆栈与之前相同。

即做:

    st.push(ar1[i]);
    generateArrays(ar1, ar2, i, index_of_b + 1, st, false);

将使堆栈不受影响。

第一个电话: generateArrays(A, B, i, 0, st, false);

从此循环生成 3 个方法调用:

    for (int i = index_of_a; i < ar1.length; i++) {
        if (ar1[i] > ar2[index_of_b]) {
            st.push(ar1[i]);
            generateArrays(ar1, ar2, i, index_of_b + 1, st, false);
        }
    }

堆栈包含值 [10]、[15] 和 [25]。

[10,30]

当 stack 为 [10] 时，它会进入前一个循环并生成 2 个调用:

    for (int j = index_of_b; j < ar2.length; j++) {
        if (ar1[index_of_a] < ar2[j]) {
            st.push(ar2[j]);
            System.out.println(st);
            generateArrays(ar1, ar2, index_of_a + 1, j, st, true);
        }
    }

堆栈包含值 [10, 20]、[10, 30] 并如您所见打印出来。

[15,30]

当 stack 为 [15] 时，它会进入前一个循环并生成 2 个调用:

    for (int j = index_of_b; j < ar2.length; j++) {
        if (ar1[index_of_a] < ar2[j]) {
            st.push(ar2[j]);
            System.out.println(st);
            generateArrays(ar1, ar2, index_of_a + 1, j, st, true);
        }
    }

堆栈包含值 [15, 20]、[15, 30] 并将它们打印出来。

编辑:进一步解释为什么 generateArrays 总是以另外一个 pop 结束:

generateArrays 将立即弹出(基本情况):

if (index_of_a >= ar1.length || index_of_b >= ar2.length) {
    st.pop();
    return;
}

或者最后弹出:

st.pop();

所有 push + generateArrays 将导致 +1 push 和 +1 pop(根据上面的参数)，堆栈保持不变。