在Java中，如何生成NxM布尔数组的每种可能的组合？

Question

我正在尝试创建一个函数来计算2D NxM数组的所有可能的NxM组合。它将能够接受介于1和N之间的任何两个整数（包括1和N）（因此对1x1、2x2、1x2、2x1 ... ... NxM执行此操作应该是可能的）。我一直在尝试不同的解决方案，但似乎无法全部计算出来。这是我到目前为止的内容：

    private static void computeGrid(int[][] B) {
        computeGrid(B,0,0);
    }

    private static void computeGrid(int[][] B, int x, int y) {
        print(B);
        int[][] B0x = copy2DArray(B);
        int[][] B0y = copy2DArray(B);
        int[][] B1x = copy2DArray(B);
        int[][] B1y = copy2DArray(B);
        if(x+1 < B0x.length) {
            B0x[x][y] = 0;
            computeGrid(B0x, x+1,y);
        }
        if(y+1 < B0y[0].length) {
            B0y[x][y] = 0;
            computeGrid(B0y, x, y+1);
        }
        if(x+1 < B1x.length) {
            B1x[x][y] = 1;
            computeGrid(B1x, x+1, y);
        }
        if(y+1 < B1y[0].length) {
            B1y[x][y] = 1;
            computeGrid(B1y, x, y+1);
        }
    }

例如，如果有一个2x2数组（表示这个的整数），我期望以下内容：

{{0,0},{0,0}}, {{0,0},{0,1}}, {{0,0},{1,0}}, {{0,0},{1,1}}, 
{{0,1},{0,0}}, {{0,1},{0,1}}, {{0,1},{1,0}}, {{0,1},{1,1}}, 
{{1,0},{0,0}}, {{1,0},{0,1}}, {{1,0},{1,0}}, {{1,0},{1,1}}, 
{{1,1},{0,0}}, {{1,1},{0,1}}, {{1,1},{1,0}}, {{1,1},{1,1}}

但是，我得到的是这个：

{{0,0},{0,0}},
{{0,0},{1,0}},
{{0,1},{0,0}},
{{1,0},{0,0}},
{{1,0},{1,0}},
{{1,1},{0,0}}

如何计算所有组合？

Answer 1

如果考虑一下，您可以将矩阵看作一维列表，其中每个元素的位置为m*N + n； m是该行的索引，n是该行的索引，N是一行中的元素数。

将矩阵视为列表可将问题简化为仅包含M*N和0的大小为1的列表的所有排列。

我们可以通过将0和1递归添加到每个排列中来使用递归来获取所有排列。递归从一个空列表开始。然后列表被复制。 0添加到原始列表，1添加到复制的列表。当我们用结果列表重复该过程直到它们到达M*N时，我们得到了排列的集合。

当我们有了这些置换时，我们可以从中取出阵列，其中每个阵列都是置换矩阵中的一行。我们可以从置换列表中的位置获取元素所属行的索引以及该行中位置的索引。

我在这里实现了该算法：

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Main {

    static void addPermutations(Deque<int[]> stack, int[] permutation, int index) {
        if (index >= 0) {
            // clone for next recursion
            int[] permutationClone = permutation.clone();

            // one gets 0, the other 1 at index
            permutation[index] = 0;
            permutationClone[index] = 1;

            // next recursion
            addPermutations(stack, permutation, index - 1);
            addPermutations(stack, permutationClone, index - 1);
        }
        else {
            stack.push(permutation);
        }
    }


    static Deque<int[][]> getPermutations(int M, int N) {
        int permutationSize = M*N;

        // get all permutations that the matrices are base on
        Deque<int[]> permutations = new ArrayDeque<>();
        addPermutations(permutations, new int[permutationSize], permutationSize - 1);

        // container for resulting matrices
        Deque<int[][]> permutationMatrices = new ArrayDeque<>();

        // for each matrix
        for (int i = permutations.size() - 1; i >= 0 ; i--) {
            int[][] matrix = new int[N][M];
            int[] permutation = permutations.pop();

            // for each row add part of permutation
            for (int j = 0; j < matrix.length; j++) {
                matrix[j] = Arrays.copyOfRange(permutation, j*M, (j + 1)*M);
            }

            // and push the matrix to result
            permutationMatrices.push(matrix);
        }
        return permutationMatrices;
    }


    public static void main(String[] args) {
        int N = 2, M = 2;
        Deque<int[][]> permutations = getPermutations(N, M);

        permutations.forEach(m -> {
            System.out.println("----");
            for (int i = 0; i < m.length; i++) {
                System.out.println(Arrays.toString(m[i]));
            }
            System.out.println("----");
        });
    }
}