The Balanced 1-0 Matrix Problem

This post is about the Balanced 1-0 Matrix problem. Namely, for an n-by-n matrix (can be relaxed to n-by-m, but we will stick to square matrix here), how many legitimate assignments are there such that each row as well as column contains exactly n/2 zeros and n/2 ones?

You will find different approaches to solve this problem in the link, and one thing to note is how quickly the sequence grows: the numbers of possible assignments are 1, 2, 90, 297200... for 1-by-1, 2-by-2, 3-by-3, 4-by-4 matrices. The brute force approach is not very interesting, so we will only discuss the dynamic programming approach. The Matlab script can be found at the end.

The idea is first to have an easy way to store the arrangement. That is what stateArr does. As a 2-by-n array, it stores how many zeros and ones are still available to be allocated for each of the n columns. Then we have the systematic sweeping through the rows, meaning that we do a tree search starting from the first row downward. We iterate all the possible combinations (of course, they have to have n/2 zeros and n/2 ones) for a row, and compare these possible combinations against the stateArr to see if there are enough zeros and ones to be assigned. This is what the for loop within the DP_recursion is for.

Finally, the algorithm described above would have to visit every and all solutions unless we use a memoization trick. All partial solutions, as well as the corresponding stateArr, are stored in stateArrTable, and for every step the script would first check whether partial solution already exists. If so, use the stateArr as a signature/key to retrieve it; if not, and only if not, will it jump into recursion.

Unfortunately, even with dynamic programming, the computation is too intensive for Matlab for any n > 4.



function output = ZeroOneMat_DP(numCol)
% ((1, 2) (2, 1) (1, 2) (2, 1)) would be stored as
% [1, 2, 1, 2; 2, 1, 2, 1]
% First row is # zeros, second row is # ones
stateArr = numCol/2*ones(2,numCol);
stateArrTable = [];
partialAnsArr = [];
[output stateArrTable partialAnsArr] = DP_recursion(numCol, stateArr, stateArrTable, partialAnsArr, 0);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [output stateArrTable partialAnsArr] = DP_recursion(numCol, stateArr, stateArrTable, partialAnsArr, numSol)
% Iterate all combinations
locationMat = nchoosek(1:numCol,numCol/2);
tempOutput = numSol;
for i = 1:size(locationMat,1)
    thisRow = zeros(1,numCol);
    thisRow(locationMat(i,:)) = 1;
    % Change stateArr
    stateArr_temp = stateArr;
    for j = 1:numCol
        if thisRow(j) == 0
            stateArr_temp(1,j) = stateArr_temp(1,j) - 1;
        elseif thisRow(j) == 1
            stateArr_temp(2,j) = stateArr_temp(2,j) - 1;
        end
    end
    % Check if there is negative values
    if min(min(stateArr_temp)) < 0
       
    elseif min(min(stateArr_temp)) >= 0 & max(max(stateArr_temp)) > 0
        % See if already in table
        [foundBool theAnswer] = findInTable(stateArr_temp, stateArrTable, partialAnsArr);
        if foundBool == 0 % not
            [tempOutput2 stateArrTable partialAnsArr] = DP_recursion(numCol, stateArr_temp, stateArrTable, partialAnsArr, tempOutput);
            % Save to partial answers
            stateArrTable = [stateArrTable; stateArr_temp];
            partialAnsArr = [partialAnsArr; tempOutput2 - tempOutput];
            tempOutput = tempOutput2;
        elseif foundBool == 1
            % find in table
            tempOutput = tempOutput + theAnswer;
        end
    elseif  max(max(abs(stateArr_temp))) == 0 % successfully placed all numbers through the last row
        tempOutput = tempOutput + 1;
    end
end
output = tempOutput;
end

function [foundBool theAnswer] = findInTable(stateArr, stateArrTable, partialAnsArr)
foundBool = 0;
theAnswer = -1;
for i = 1:size(stateArrTable,1)/2
    if max(max(abs(stateArrTable(2*i-1:2*i,:)-stateArr))) == 0
        theAnswer = partialAnsArr(i);
        foundBool = 1;
        break
    end
end
end