0 1 équilibrage matriciel

Question

Sur wikipedia http://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0.E2.80.931_matrix, le nombre de matrices équilibrées 0 1 est donné à titre d'exemple de programmation dynamique. Mais j'ai trouvé très difficile d'implémenter l'algorithme donné ici. Y a-t-il un meilleur algorithme? Si ce n'est pas le cas, alors quelqu'un peut-il expliquer l'algorithme présenté ici d'une manière qui le rend plus facile à implémenter. Comme quelle serait la relation de récurrence dans cet algorithme? Parce qu'une fois que je l'ai trouvé, il serait facile de faire une mémo.

Aussi peut-on dire pourquoi ce problème particulier semble tellement plus difficile que tous les autres problèmes donnés sur cette page.

Answer 1

La programmation dynamique serait plus rapide, mais voici un moyen simple pour l'énumération. Matrice équilibrée: matrice 0-1 bicolore. Ici s est la dimension de la matrice carrée équilibrée 0-1, L [p] [q] est une entrée de la matrice. Appelez d'abord énumération (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

solution de programmation dynamique

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


    } 



}