remove all ones from matrix in combinantion
2 次查看(过去 30 天)
显示 更早的评论
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.
10 个评论
Guillaume
2020-3-6
I wrote my solution before seeing the updates. I'm still unclear on exactly what you're trying to achieve. Two common problem that appear to be related are the Maximum coverage problem and the set cover problem. Is this what you're after?
As explained, my solution will find all the covers. However, it's easy to change the recursion function so that it discards covers that fully encompass other covers.
采纳的回答
Guillaume
2020-3-6
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);
7 个评论
Guillaume
2020-4-3
I'm not sure I understand what you're trying to do. break is only useful inside a for or while loop.Where you used it, it does nothing.
Also, note that I gave all my variables a meaningful name. I suggest that you continue that pattern instead of using B, n and d.
更多回答(0 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Data Type Identification 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!