Generating all variations of M*N matrix containing boolean values

Question

I've implemented an algorithm that generates all variations of a matrix of size \$M*N\$. My approach is that I see a matrix as a list where the position of elements can be calculated from the position in the matrix. By doing that I can reduce the problem into generating all variations of a list of length \$M*N\$.

The algorithm computes the variations recursively. I start with an empty list and pass it to my function. The list is copied. The copied list gets a 0 and the original list gets a 1 added. Then I call the function recursively with each of both resulting lists. The process is repeated until the length \$M*N\$ is reached. At this point, I have the set of all variations (size = \$2^{M*N}\$).

Now I can compute the arrays from those variations and compose the resulting matrices.

Here is the implementation:

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("----");
        });
    }
}

I'd be very happy to get tipps on how to improve the code. I'm especially interested in style and readability of my code.

---

The expected output is the set of variations. Each variation is a matrix containing only 0s and 1s. Each matrix is represented as a 2-dimensional array where each row is an array.

So e.g. the output for a \$2*2\$ matrix is supposed to be:

[[0, 0], [0, 0]], [[1, 0], [0, 0]], [[0, 1], [0, 0]], [[1, 1], [0, 0]],

[[0, 0], [1, 0]], [[1, 0], [1, 0]], [[0, 1], [1, 0]], [[1, 1], [1, 0]],

[[0, 0], [0, 1]], [[1, 0], [0, 1]], [[0, 1], [0, 1]], [[1, 1], [0, 1]],

[[0, 0], [1, 1]], [[1, 0], [1, 1]], [[0, 1], [1, 1]], [[1, 1], [1, 1]]

The order doesn't matter.

Answer 1

The code does not produce permutations. It produces the subsets of \$M * N\$-strong set. Below assumes that it is the goal of the code.

Recursive solution is correct, but may take too much memory (there are exponentially many subsets, namely \$2^{N*M}\$ of them). I strongly recommend to switch to an iterative approach:

    bool next_subset(int [] subset) {
        for (int i = 0; i < subset.size(); i++) {
            if subset[i] == 1) {
                subset[i] == 0;
            } else {
                subset[i] = 1;
                return true;
            }
        }
        return false;
    }

which takes the same time, linear memory, and can be used to stream the subsets one-by-one.