How to fill a matrix with 0 and 1 recursively?

Question

Ok so my problem is basically, I have a matrix for example

010
101
111

just random 1s and 0s. So I have arrays that are rowcount and colcount, which count the number of ones in each row and column. So rowcount for this is {1,2,3} and colcount is {2,2,2}. Now in another method, I am given the arrays rowcount and colcount, and in that method, I am supposed to create a matrix with the counts in rowcount and colcount, but the end matrix can be different. Than the original. I think I'm supposed to exhaust all permutations until a matrix works. The base case must stay the same.

Note: Math.random cannot be used.

private static void recur(int[][] m, int[] rowcount, int[] colcount, int r, int c) 

//recursive helper method

 {

if(compare(m, rowcount, colcount))    //base case: if new matrix works

{

System.out.println();

        System.out.println("RECREATED");

        display(m, rowcount, colcount);    //we're done!

        System.exit(0);

     }

     else

     { 
        int[] temp_r = new int[m.length];

        int[] temp_c = new int[m[0].length];

 count(m, temp_r, temp_c);

        if(rowcount[r] > temp_r[r] && colcount[c] > temp_c[c])

           m[r][c] = 1;

        if(r+1 < m.length)

           recur(m,rowcount,colcount,r+1,c);

        if(rowcount[r] < temp_r[r] || colcount[c] < temp_c[c])

           m[r][c] = 0;

        if(c+1 < m[0].length)

           recur(m,rowcount,colcount,r,c+1);     

     }

  }

private static boolean compare(int[][] m, int[] rowcount, int[] colcount)

{
 int[] temp_r = new int[m.length];

 int[] temp_c = new int[m[0].length];

 count(m, temp_r, temp_c);



 for (int x = 0; x < temp_r.length; x++)

 {

    if(temp_r[x] != rowcount[x])

       return false;

 }



 for (int y = 0; y < temp_c.length; y++)

 {

    if(temp_c[y] != colcount[y])

       return false;

 }

 return true; 

  }

public static void count(int[][] matrix, int[] rowcount, int[] colcount)

{

  for(int x=0;x<matrix.length;x++)

     for(int y=0;y<matrix[0].length;y++)

     {

        if(matrix[x][y]==1)

        {

           rowcount[x]++;

           colcount[y]++;

        }

     }

  }

Answer 1

Well, I decided I'd implement a solution, but instead of Java (which you haven't actually specified the solution needs to be in), I'm going to use Groovy (which is Java based anyway)! I've tried to use Java syntax where possible, it's not hard to extrapolate the Java code from this (but it is much more verbose!)

Note:

*Generating a random bit matrix, not using Math.random()

*I'm storing my matrix in a string i.e. [[0,1],[1,0]] = "0110"

*My solution relies heavily, on converting Integers to/from BinaryStrings (which is essentially what your matrix is!)

// Generate random matrix
int colSize = 3;
int rowSize = 4;
String matrix = '';
for (int i = 0; i < rowSize; i++){
    String bits = Integer.toBinaryString(System.currentTimeMillis().toInteger());
    matrix += bits.substring(bits.length() - colSize);
    Thread.sleep((System.currentTimeMillis() % 1000) + 1);
}
def (cols1,rows1) = getCounts(matrix, colSize)
println "matrix=$matrix rows1=$rows1 cols1=$cols1"

// Find match (brute force!)
int matrixSize = colSize * rowSize
int start = 0
int end = Math.pow(Math.pow(2, colSize), rowSize) // 2 is number of variations, i.e. 0 and 1
for (int i = start; i <= end; i++){
    String tmp = leftPad(Integer.toBinaryString(i), matrixSize, '0')
    def (cols2,rows2) = getCounts(tmp, colSize)
    if (cols1 == cols2 && rows1 == rows2){
        println "Found match! matrix=$tmp"
        break;
    }
}
println "Finished."
String leftPad(String input, int totalWidth, String padchar){ String.format('%1$' + totalWidth + "s", input).replace(' ',padchar) }
int[][] getCounts(String matrix, int colSize){
    int rowSize = matrix.length() / colSize
    int[] cols = (1..colSize).collect{0}, rows = (1..rowSize).collect{0}
    matrix.eachWithIndex {ch, index -> 
        def intval = Integer.parseInt(ch)
        cols[index % colSize] += intval
        rows[(int)index / colSize] += intval
    }
    [cols,rows]
}

Gives output:

matrix=001100011000 rows1=[1, 1, 2, 0] cols1=[1, 1, 2]
Found match! matrix=001001110000
Finished.

Brute force search logic:

Given a rowcount of [1,2,3]
And a colcount of [2,2,2]
Iterate over all matrix combinations (i.e. numbers 0 - 511 i.e. "000000000" -> "111111111")
Until the new matrix combination's rowcount and colcount matches the supplied rowcount and colcount

Answer 2

OK, your question and comments indicate you are on the right track. The code itself is a bit messy and it has obviously gone through some iterations. That's not great, but it's OK.

You are right, I believe, that you have to 'exhaust' the recursion until you find a new result that matches the existing column/row counts. So, attack the problem logically. First, create a method that can compare a matrix with a row/column count. You call it 'compare(...)'. I assume this method you have already works ;-). This is the method that marks the end of the recursion. When compare returns true, you should return up the recursion 'stack'. You should not do a System.exit(...).

So, the basic rule of recursion, you need an input, output, a method body that contains an exit-condition check, and a recursive call if the condition is not met....

Your problem has a specific issue which complicates things - you need to make copies if the input matrix every time you go down a recursion level. Alternatively you need to 'undo' any changes you make when you come up a level. The 'undo' method is faster (less memory copies).

So, the process is as follows, start with an all-zero matrix. Call your recursive function for the all-zero start point.

int[][] matrix = new int[width][height];
int rpos = 0;
boolean found = recur(matrix, rowcount, colcount, 0, 0);

This is how it will be called, and found will be true if we found a solution.

The difference here from your code is that recur now returns a boolean.

So, our recur method needs to do: 1. check the current matrix - return true if it matches. 2. make meaningful changes (within the limits that we've added) 3. recursively check the change (and add other changes).

Your method does not have an output, so there's no way to escape the recursion. So, add one (boolean in this case).

The way this can work is that we start in the top left, and try it with that bit set, and with it unset. For each contition (set or unset) we recursively test whether the next bit matches when set, or unset, and so on.... :

private static boolean recur(int[][] m, int[] rowcount, int[] colcount, 
        int row, int col) {
    if (compare(m, rowcount, colcount)) {
        // our matrix matches the condition
        return true;
    }
    if (row >= m.length) {
        return false;
    }

    int nextcol = col + 1;
    int nextrow = row;
    if (nextcol >= m[row].length) {
        nextcol = 0;
        nextrow++;
        if (nextrow > m.length) {
            return false;
        }
    }
    // OK, so nextrow and nextcol are the following position, and are valid.
    // let's set our current position, and tell the next level of recursion to
    // start playing from the next spot along
    m[row][col] = 1;
    if (recur(m, rowcount, colcount, nextrow, nextcol)) {
        return true;
    }
    // now unset it again
    m[row][col] = 0;
    if (recur(m, rowcount, colcount, nextrow, nextcol)) {
        return true;
    }
    return false;

}

The above code is just hand-written, it may have bugs, etc. but try it. The lesson in here is that you need to test your consitions, and you need a strategy....