java - 打印二维矩阵中所有元素的组合

Question

打印大小为 m * n 的矩阵中所有元素的组合。

示例示例:
1 3 5
2 6 7

预期输出:
2 , 1
2 , 3
2 , 5
6 , 1
6 , 3
6 , 5
7 , 1
7 , 3
7、5

规则:
- 每个组合都从矩阵的底部开始并向顶部前进。不过它可能会切换列。
- 每个组合的元素数量应等于行数。
- 组合中同一行的元素不能出现两次。

我从来没有想出一般情况下的解决方案。我可以使用 3 个循环。但是我想了解递归解决方案。我使用 Java。

Answer 1

这里有一个非递归的方法来解决这个问题(它不是很漂亮，但它适用于您的输入)。我知道你对递归很感兴趣，但我现在没有适合你的东西。通常，由于我处理的问题的大小，我会避免递归(即使在 -Xmx60G 时，递归堆栈的大小也会导致堆空间错误)。希望这会有所帮助。

private static List<int[]> combos;
public static void main(String[] args){
    combos = new ArrayList<int[]>();
    generate(new int[][]{{1,3,5},{2,6,7}});
    for(int[] s : combos){
        System.out.println(java.util.Arrays.toString(s));
    }
}
private static void generate(int[][] elements) {
    int rows = elements.length;
    int[] elementsIndex = new int[rows];
    int[] elementsTotals = new int[rows];
    java.util.Arrays.fill(elementsTotals, elements[0].length);
    int curIdx = 0;
    int[] c = new int[rows];
    while(true){
        while(curIdx >= 0){
            if(curIdx == rows) {
                addCombo(c);
                curIdx--;
            }
            if(elementsIndex[curIdx] == elementsTotals[curIdx]){
                elementsIndex[curIdx] = 0;
                curIdx--;
            } else break;
        }
        if(curIdx < 0) break;
        // toggle order: 
        //  bottom up: elements[rows-curIdx-1][elementsIndex[curIdx]++]
        //  top down: elements[curIdx][elementsIndex[curIdx]++]
        c[curIdx] = elements[rows-curIdx-1][elementsIndex[curIdx]++];
        curIdx++;
    }
}
private static void addCombo(int[] c){
    int[] a = new int[c.length];
    System.arraycopy(c, 0, a, 0, c.length);
    combos.add(a);
}