MATLAB: Remove all ones from matrix in combinantion

remove all ones from matrix in combinantion

I have A
A=[0 0 0 0 0 0 0 0 0 0;
0 0 0 1 0 1 0 0 0 0;
0 0 0 1 1 0 0 0 0 0;
0 0 0 0 0 1 0 0 0 0;
0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 ];
this matrix has 1 in (R2, R3, R4) and (C4, C5, C6) R correspond to row and C correspond to column.
I want to find combination like below to remove all 1 from matrix. So each R2,R3,R4, C4, C5, C6 should be participate on this.
This is example of combination that I write here. I think it would be better way to do this.
R2 R3 R4 C4 C5 C6
-------------------------------------------------------------------
combination 1: 0 0 0 1 1 1 ---> remove(C4,C5,C6) --> we remove all ones in A (Removed columns or rows is shown by 1)
combination 2: 0 0 1 1 1 1 ---> remove(R4,C4,C5,C6) --> we remove all ones in A
combination 3: 0 1 0 1 0 1 ---> remove(R3,C4,C6) --> remove all ones in A
combination 4: 0 1 1 1 0 1 ---> remove(R3,R4,C5,C6) --> remove all ones in A
combination 5: 1 0 0 1 1 1 ---> remove(R2,C4,C5,C6) --> remove all ones in A
combination 6: 1 0 1 1 1 0 ---> remove(R2,R4,C4,C5) --> remove all ones in A
I do not know how to remove ones from matrix A, by using this combination.

Best Answer

Your problem is a covering problem. A search on the file exchange may find some solutions there.
I've not understand your after that. The code doesn't make sense to me.
The following gives you all valid combinations of rows and columns that cover all the 1s in your input matrix. The format is different than your desired cell array as I believe the output here is more useful. It's trivial to transform it into your desired format
function covers = findallcoverages(A)
%inputs
% A: A matrix of 0 and 1. Maximum size of any dimension is 65535
%outputs
% A cell array of 2D matrices. Each matrix represent a valid combination of rows and columns which cover all the 1s in A
% The 1st column of each matrix is a row or column index
% The 2nd column indicates whether the corresponding index is a row (1) or a column (0)
%prepare for recursion
[rows, cols] = find(A);
wholeset = [rows, cols];
urows = unique(rows); ucols = unique(cols);
%all work done by the recursive function. starting cover is made up of all rows and columns, which is always valid
covers = findvalidcoverages([urows, ones(size(urows)); ucols, zeros(size(ucols))], wholeset);
%there's probably going to be some duplicates going through the recursion. Remove them
%unfortunately unique is not implemented for cell arrays of numerics. It is for char vector, so temporarily convert to char and back
%As long as row/columns indices are less than intmax('uint16') we're fine.
ccovers = cellfun(@(c) reshape(char(c), 1, []), covers, 'UniformOutput', false); %convert to char row vectors.
ccovers = unique(ccovers); %remove duplicate
covers = cellfun(@(cc) reshape(double(cc), [], 2), ccovers, 'UniformOutput', false); %convert back to double
end
function subsets = findvalidcoverages(subset, wholeset)
%subset: 2 columns matrix. 1st column: column or row index
% 2nd column: indicates whether the element in the 1st column is a row (1) or column index
%wholeset: 2 columns matrix, result of find. 1st column: row indices of the 1, 2nd column: column indices of the 1
%Have we got a coverage of wholeset ?
isrow = subset(:, 2) == 1;
covered = all(ismember(wholeset(:, 1), subset(isrow, 1)) | ismember(wholeset(:, 2), subset(~isrow, 1)));
if covered
%yes
subsets = {subset}; %at least this one is valid
%try reducing the subset by removing another row or column
for ridx = 1:size(subset, 1)
subsubsets = findvalidcoverages(subset([1:ridx-1, ridx+1:end], :), wholeset);
if ~isempty(subsubsets)
subsets = [subsets, subsubsets]; %#ok<AGROW>We don't know how many there'll be
end
end
else
subsets = []; %not valid
end
end
To convert the result of the above in your desired cell array:
covers = findallcoverages(A);
[rows, cols] = find(A);
rows = unique(rows); cols = unique(cols);
wholeset = [rows, ones(size(rows)); cols, zeros(size(cols))];
colnames = [compose('R%d', rows); compose('C%d', cols)];
[~, removed_indices] = cellfun(@(c) ismember(c, wholeset, 'rows'), covers, 'UniformOutput', false);