0 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;
}

Решение для динамического программирования

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


    }



}