0 1 矩阵平衡

Question

在维基百科http://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0。 E2.80.931_matrix，统计0 1平衡矩阵的个数为给出动态规划的例子。但我发现实现那里给出的算法真的很难。有更好的算法吗？

如果没有，那么任何人都可以以一种更容易实现的方式解释那里提出的算法。这个算法中的递归关系是什么？因为一旦我找到了它，记忆起来就很容易了。

任何人都可以告诉为什么这个特定问题看起来比该页面上给出的所有其他问题困难得多。

Answer 1

动态编程会更快，但这里有一个简单的枚举方法。
平衡矩阵：双色0-1矩阵。这里s是0-1平衡方阵的维数，L[p][q]是矩阵的一个条目。最初调用 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;
}

Answer 2

动态规划解决方案

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();
        }


    }



}