Generating all variations of M*N matrix containing boolean values 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&lt;int[]&gt; stack, int[] variation, int index) {
        if (index &gt;= 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&lt;int[][]&gt; 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&lt;int[]&gt; variations = new ArrayDeque&lt;&gt;();
        addVariations(variations, new int[variationLength], variationLength - 1);

        // container for resulting matrices
        Deque&lt;int[][]&gt; variationMatrices = new ArrayDeque&lt;&gt;();

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

            // for each row add part of variation
            for (int j = 0; j &lt; 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&lt;int[][]&gt; variations = getVariations(N, M);

        variations.forEach(v -&gt; {
            System.out.println("----");
            for (int i = 0; i &lt; 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.
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 &lt; 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.