remove all ones from matrix in combinantion

Question

NA 2020-3-6

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/509413-remove-all-ones-from-matrix-in-combinantion

评论： Guillaume 2020-4-3

I have A

A=[0 0 0 0 0 0 0 0 0 0; 
0 0 1 0 1 0 0 0 0; 
0 0 1 1 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 ];

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 个评论
显示 8更早的评论隐藏 8更早的评论

NA 2020-3-6

编辑：NA 2020-3-10

在 MATLAB Online 中打开

in mentioned example

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 ];
                   R2   R3   R4   C4   C5   C6
             -------------------------------------------------------------------
combination 1:     0    0    0     1    1    1 ---> save[4,5,6] (C4 correspond to index 4 in matrix B)
combination 2:     0    0    1     1    1    1 ---> save[4,5,6] (this step can be skipped as this is the same as previous step)
combination 3:     0    1    0     1    0    1 ---> save [3,4,6]
combination 4:     0    1    1     1    0    1 ---> save [3,4,6] (this step can be skipped as this is the same as previous step)
combination 5:     1    0    0     1    1    1 ---> save[2,4,5,6]
combination 6:     1    0    1     1    1    0 ---> save [2,4,5,6] (this step can be skipped as this is the same as previous step)

result should be:

removed_index={[4,5,6];[3,4,6];[2,4,5,6]}

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.

NA 2020-3-10

编辑：NA 2020-3-10

I do not know how to change recursion function to discard repeated covers.

for example [4,0; 5 0; 6 0] is repeated 6 times.

[3 1; 4 0; 6 0] is repeated 6 times.

[2 1; 3 1; 4 1] is repeated 6 times.

[2 1; 3 1; 6 0] is repeated 6 times.

Is there any way to do this?

Also for atteched file, finding covers will be time consuming. But I do not know how to make recursion function faster.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Guillaume 2020-3-6

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/509413-remove-all-ones-from-matrix-in-combinantion#answer_418910

在 MATLAB Online 中打开

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

7 个评论
显示 5更早的评论隐藏 5更早的评论

Guillaume 2020-3-10

在 MATLAB Online 中打开

"how can I change the recursion function so that it discards covers that fully encompass other covers?"

Change the recursive function to:

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)));
    subsets = [];  %initial value and return value if the current subset is not a cover
    if covered
        %yes, 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
        if isempty(subsets)  %we didn't find any smaller coverage
            subsets = {subset};  %the current subset works
        end
    end
end

The main function findallcoverages stays the same.

" finding covers will be time consuming."

Yes, my solution is

where n is the number of 1. As I wrote in my answer, you may want to search the file exchange other implementations. You should also read the wikipedia in my comment to the question. In particular, it does sound like you're trying to solve the set cover problem, for which my algorithm is certainly not optimal. It's a well known problem, I'm sure you can find some algorithms a lot more efficient than mine.

However, note that it is a NP-complete problem which wikipedia will tell you are "informally described as the "hardest" problems in NP".

NA 2020-4-3

编辑：NA 2020-4-3

在 MATLAB Online 中打开

By finding one subset I want use sample_function and check some condition and break this recursive function how can I do this?

Also is it the correct way to change input of sample_function in ubsets = findvalidcoverages(subset, wholeset, B,N,d) and subsubsets = findvalidcoverages(subset([1:ridx-1, ridx+1:end], :), wholeset,B,N,d);

function subsets = findvalidcoverages(subset, wholeset, B,N,d)
   
    isrow = subset(:, 2) == 1;
    covered = all(ismember(wholeset(:, 1), subset(isrow, 1)) | ismember(wholeset(:, 2), subset(~isrow, 1)));
    subsets = [];  %initial value and return value if the current subset is not a cover
    if covered
        %yes, 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,B,N,d);
            if ~isempty(subsubsets)
                subsets = [subsets, subsubsets];  %#ok<AGROW>We don't know how many there'll be
            end
        end
        if isempty(subsets)  %we didn't find any smaller coverage
            subsets = {subset};  %the current subset works
        
        %% New function    
         [remain] = sample_function(B,N,d);
        if isempty(remain)
                    break   % break function
        end
   
            
            
        end
    end
end