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

Question

我正在尝试创建一个函数来计算二维 NxM 数组的所有可能的 NxM 组合。它将能够包含 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 的列表的所有变体 (2^(M*N))。

我们可以利用递归来获取所有变体，方法是将 0s 和 1s 递归地添加到每个变体。递归以一个空列表开始。然后复制列表。 0 被添加到原始列表，1 被添加到复制的列表。当我们对结果列表重复该过程直到它们达到 M*N 时，我们得到了变化集。

当我们有这些变化时，我们可以从中得到数组，其中每个数组都是矩阵变化中的一行。我们可以从变化列表中的位置获取元素所属行的索引和行中位置的索引。

我在这里实现了该算法：

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

class Main {

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

            // one gets 0, the other 1 at index
            variation[index] = 0;
            variationClone[index] = 1;

            // next recursion
            addVariations(stack, variation, index - 1);
            addVariations(stack, variationClone, index - 1);
        }
        else {
            stack.push(variation);
        }
    }


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

        // get all variations that the matrices are base on
        // there are n^r, 2^variationLength of them
        Deque<int[]> variations = new ArrayDeque<>();
        addVariations(variations, new int[variationLength], variationLength - 1);

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

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

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

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


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

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

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

In Java, how do you generate every possible combination of an NxM boolean array?

java

arrays

combinations

2d