0 1 matrix balancing

Question

On wikipedia http://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0.E2.80.931_matrix, counting the number of 0 1 balanced matrices is given as an example of dynamic programming. But I found it really hard to implement the algorithm given there. Is there a better algorithm?

If not, then can anyone kindly explain the algorithm presented there in a way that makes it easier to implement. Like what would be the recurrence relation in this algorithm? Because once I have found it, it would be easy to do memoization.

Also can any one tell that why this particular problem seems so much harder than all the other problems given on that page.

Answer 1

Dynamic programming solution

import java.util.HashMap;
import java.util.Map;

public class Balanced01Matrix {

    //Variable to hold all possible row permutation 
    private int[][] rowPerms;

    //Mapping function f((n/2,n/2),(n/2,n/2)......(n/2,n/2))
    Map<String, Integer> arrangeFunction;

    int rowCounter = 0;

    /**
     * @param args
     */
    public static void main(String[] args) {
        Balanced01Matrix bm = new Balanced01Matrix();
        int n = 4;
        int rows = bm.combination(n, n/2);
        bm.rowPerms = new int[rows][n];
        //Getting all the row permuation with n/2 '0' and n/2 '1'
        bm.getAllCombination(n/2, n/2, n, new int[n]);
        //bm.printAllCombination();
        bm.arrangeFunction = new HashMap<String, Integer>();
        //Variable to hold vector ((n/2,n/2),(n/2,n/2),......(n/2,n/2))
        int[][] digitsRemaining = new int[n][2];
        for(int i=0;i<n;i++){
            digitsRemaining[i][0]=n/2;
            digitsRemaining[i][1]=n/2;
        }
        //Printing total number of combination possible for nxn balanced matrix
        System.out.println(bm.possibleCombinations(digitsRemaining, n));
    }

    /**
     * Method to get all permutation of a row with n/2 zero and n/2 one
     * @param oneCount
     * @param zeroCount
     * @param totalCount
     * @param tmpArr
     */
    private void getAllCombination(int oneCount, int zeroCount, int totalCount, int[] tmpArr){
        if(totalCount>0){
            if(oneCount > 0){
                tmpArr[totalCount-1] = 1;
                getAllCombination(oneCount-1, zeroCount, totalCount-1, tmpArr);
            }
            if(zeroCount > 0){
                tmpArr[totalCount-1] = 0;
                getAllCombination(oneCount, zeroCount-1, totalCount-1, tmpArr);
            }
        }else{
            rowPerms[rowCounter++] = tmpArr.clone();
        }

    }

    /**
     * Recursive function to calculate all combination possible for a given vector and level
     * @param digitsRemaining
     * @param level
     * @return
     */
    private int possibleCombinations(int[][] digitsRemaining, int level){
        //Using memoization
        if(arrangeFunction.containsKey(getStringForDigitsRemaining(digitsRemaining))){
            return arrangeFunction.get(getStringForDigitsRemaining(digitsRemaining)); 
        }
        int totalCombination = 0;
        for(int[] row: rowPerms){
            int i=0;
            int[][] tmpArr = createCopy(digitsRemaining);
            for(;i<row.length;i++){
                if(row[i]==0){
                    if(tmpArr[i][0] - 1 >= 0){
                        tmpArr[i][0] -= 1;
                    }else
                        break;
                }else{
                    if(tmpArr[i][1] - 1 >= 0){
                        tmpArr[i][1] -= 1;
                    }else
                        break;
                }
            }
            //If row permutation is successfully used for this level
            //else try next permuation
            if(i==row.length){
                //If last row of matrix return 1
                if(level == 1){
                    return 1;
                }else{
                    int combinations = possibleCombinations(tmpArr, level-1);
                    arrangeFunction.put(getStringForDigitsRemaining(tmpArr), combinations);
                    totalCombination += combinations;
                }
            }
        }
        return totalCombination;
    }

    /**
     * Creating deep copy of 2 dimensional array
     * @param arr
     * @return
     */
    private int[][] createCopy(int[][] arr){
        int[][] newArr = new int[arr.length][arr[0].length];
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length;j++){
                newArr[i][j] = arr[i][j];
            }
        }
        return newArr;
    }

    private void printRow(int[] row){
        for(int i: row)
            System.out.print(i);
    }

    private String getStringForDigitsRemaining(int[][] digitsRemaining){
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<digitsRemaining.length;i++){
            sb.append(digitsRemaining[i][0]);
            sb.append(digitsRemaining[i][1]);
        }
        return sb.toString();
    }

    /**
     * Calculates x choose y
     * @param x
     * @param y
     */
    private int combination(int x, int y){
        if(x>0 && y>0 && x>y)
            return factorial(x)/(factorial(y)*factorial(x-y));
        else
            return 0;
    }

    private int factorial(int x){
        if(x==0)
            return 1;
        return x*factorial(x-1);

    }

    private void printAllCombination(){
        for(int[] arr: rowPerms){
            for(int i: arr)
                System.out.print(i);
            System.out.println();
        }


    }



}

Answer 2

Dynamic programming would be faster, but here is a simple way for enumeration. Balanced matrix: bicolorable 0-1 matrix. Here s is the dimension of the 0-1 balanced square matrix, L[p][q] is an entry of the matrix. Initially call enumerate(s,1,1).

int enumerate(int s, int p,int q){ 

    if(p>s) {
             printmatrix(L);
             return 0;
    }

    if(p>=3 && q>=3){
            int min = p;if(p>q){min=q;}
            if L[1...min][1...min] is not a balanced matrix, then return 0;            
    }
    if(q<=s) {
            L[p][q] = 1;
            enumerate(s,p,q+1);
            if(p!=q){
                     L[p][q] = 0;
                     enumerate(s,p,q+1);            
            }
    }
    if(q>s) {
            enumerate(s,p+1,1); 
    }
    return 0;
}