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
