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]是矩陣的一個入口。最初調用枚舉（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(); 
     } 


    } 



}