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


    } 



}