2
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Doesn't look like permutations to me. Can you add a small example of the expected output? \$\endgroup\$ – vnp May 17 '20 at 21:51
  • \$\begingroup\$ @vnp Thank you, you are right, it's about variations, not permutations. I've updated the question. \$\endgroup\$ – akuzminykh May 18 '20 at 13:50
  • \$\begingroup\$ A request was made to add a small example of the expected output. Would it be possible for you to add this? \$\endgroup\$ – Mast May 18 '20 at 14:08
  • \$\begingroup\$ @Mast There you go. \$\endgroup\$ – akuzminykh May 18 '20 at 14:17
  • \$\begingroup\$ How about just implementing a method that visualizes the binary representation of any integer between 0 and 2^(M*N) as a 2D array? \$\endgroup\$ – TorbenPutkonen May 18 '20 at 15:54
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Mast May 18 '20 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.