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.

• vnp: Doesn't look like permutations to me. Can you add a small example of the expected output?
• akuzminykh: @vnp Thank you, you are right, it's about variations, not permutations. I've updated the question.
• Mast: A request was made to add a small example of the expected output. Would it be possible for you to add this?
• akuzminykh: @Mast There you go.
• TorbenPutkonen: How about just implementing a method that visualizes the binary representation of any integer between 0 and 2^(M*N) as a 2D array?

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.

• Mast: The latest edit invalidates your answer. However, since you point out in your answer that the code didn't do what it should've been doing, perhaps it's better to simply scrap the first line of your answer instead of rolling-back the edit.