CODEWITHSUNDEEP
javamatrix
StepTNT
StepTNT

Reputation: 3967

Generating all the possible configurations of a matrix with some restrictions

I've been struggling on this for some time and I'm really confused on how to solve this problem. I've found something that works with MatLab but it's not what I need.

Here's my scenario:

private int[][] c = {{1,1,1,1,1,1,1},
                     {0,0,0,0,0,0,0},
                     {0,0,0,0,0,0,0}
                    };

c is a matrix in which I can have only one value set to 1 in each column. This means that a configuration like

private int[][] c = {{0,1,0,1,1,0,0},
                     {1,0,0,0,0,1,1},
                     {0,0,1,0,0,0,0}
                    };

is valid, while

private int[][] c = {{1,0,1,1,0,1,1},
                     {0,0,1,0,0,0,0},
                     {0,0,0,0,1,0,0}
                    };

is not. What I need is to generate a Set containing all the valid combinations for this matrix, but I've no idea on how to start. I don't know if it's just because it's late and I'm half asleep but I can't think of a good way to do this.

Do you have any ideas?

Upvotes: 0

Views: 635

Answers (1)

Marco13
Marco13

Reputation: 54649

There are many possible ways of actually implementing this. But you basically have to count from 0 to 37, and create one matrix for each number.

Imagine each possible column of the matrix as one number:

1
0 = 0
0

0
1 = 1
0

0
0 = 2
1

Then, the matrices can be represented by numbers in 3-ary form. The number 0000000 will correspond to the matrix

1 1 1 1 1 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0

The number 0000001 will correspond to the matrix

1 1 1 1 1 1 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

and so on.

Then, you can compute the total number of matrices, count up from 0 to this number, convert each number into a string in 3-ary form, and fill the matrix based on this string.

The 895th matrix will have the number 1020011, which is one of your example matrices:

 0 1 0 1 1 0 0
 1 0 0 0 0 1 1
 0 0 1 0 0 0 0

A simple implementation:

public class MatrixCombinations
{
    public static void main(String[] args)
    {
        int cols = 7;
        int rows = 3;
        int count = (int)Math.pow(rows, cols);
        for (int i=0; i<count; i++)
        {
            String s = String.format("%"+cols+"s", 
                Integer.toString(i, rows)).replaceAll(" ", "0");
            int[][] matrix = createMatrix(rows, cols, s);
            System.out.println("Matrix "+i+", string "+s);
            printMatrix(matrix);
        }
    }

    private static int[][] createMatrix(int rows, int cols, String s)
    {
        int result[][] = new int[rows][cols];
        for (int c=0; c<cols; c++)
        {
            int r = s.charAt(c) - '0';
            result[r][c] = 1;
        }
        return result;
    }

    private static void printMatrix(int matrix[][])
    {
        for (int r=0; r<matrix.length; r++)
        {
            for (int c=0; c<matrix[r].length; c++)
            {
                System.out.printf("%2d", matrix[r][c]);
            }
            System.out.println();
        }
    }
}

Upvotes: 1

Related Questions