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.

[Ameer Hamza]

Is the matrix A constant, or it can also change? Also, in this case, also give an example of a combination that is not acceptable.

[dpb]

Well, I thought maybe by rearranging the matrix to see its shape and content would be able to figure out what your other table is supposed to mean and just what it is you are trying to do...unfortumately, it didn't help; I have no klew.

While I can agree there are ones in rows 2,3,4 and columns 4,5,6 I can't decipher what the table means nor what you mean by "remove all ones in A" for the "combinations".

You can replace all 1's in A w/ NaN or some other value easily enough with

A(A==1)=nan;

or you can remove rows, columns that contain 1's in their entirety as

A(:,any(A))=[];    % remove all rows w/ 1's
A(any(A,2),:)=[];  % remove any remaining columns if any

but you can't leave "holes" in the middle of an array.

So, tell/show what you think the result should be and how you arrived at that result.

[the cyclist]

I think I understand what you are trying to do. For example, another combination that removes all 1's from A would be

remove(R2,R3,R4)

wiithout needing to mention columns. Because 1's only appear in rows 2, 3, and 4. Right?

How do you want the output reported? Suppose that your combination 1 and 2 were the only ones that worked. Would the output be a matrix like this?

output = [0    0    0     1    1    1 
          0    0    1     1    1    1];

That doesn't really tell you that the columns correspond to R2 R3 R4 C4 C5 C6. Is that OK?

Suppose

A = [0 0 0;
     0 1 0;
     0 0 1];

What is the full output that you want?

[the cyclist]

So, for others' sake, here is what I think OP wants:

Find every combination of rows and columns such that, if I remove those rows and columns, there will be no 1's in the matrix. So, for example, if

A = [0 0 0;
     0 1 0;
     0 0 1];

the combinations would be

 R2,R3
 R2,C3
 R3,C2

I'm just not certain how OP wants the output structured.

[NA]

"wiithout needing to mention columns. Because 1's only appear in rows 2, 3, and 4. Right?"

yes.

"How do you want the output reported? Suppose that your combination 1 and 2 were the only ones that worked. Would the output be a matrix like this?"

After that I want to remove calculated indices from the rows of this matrix.

B=[1,2; 3,4; 5,6; 7,8; 9,10; 11,3; 4,7; 8, 9; 6,9; 10,8]

In my case A is 0 in diagonal element and square matrix with size (10*10).

B is (10*2). So after finding this indices I can remove it from B

[NA]

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]}

[the cyclist]

I don't yet understand the operation you want to do on B. But it sounds like if

A = [0 0 0;
     0 1 0;
     0 0 1];

then all possible solutions are

 removed_index_all_rows={[2,3];[2,3];[2,3]}; % Has the redundant rows

but you don't need redundant rows, so

removed_index={[2,3]}; % Keep only unique rows

Also, can you confirm that removing

remove(R4,C4,C5,C6)

and

remove(C4,C5,C6)

are truly redundant, even though the first one has row 4, and the second one has only column 4? They would both give

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

?

[NA]

"Also, can you confirm that removing remove(R4,C4,C5,C6) and remove(C4,C5,C6)."

yes. R4 and C4 both correspond to index 4 in B.

[Guillaume]

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]

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]

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

[NA]

I got this result

removed_indices={[1;2;3],[1;2;3;4],....}

but I don't have any one element in index 1. should be

removed_indices={[2;3;4],...}

[Guillaume]

Please do read the comments in the code I wrote. If you want row/column indices it's in the covers variable which contains 2 columns matrices, 1st column is row/column index, 2nd column is 1 if the 1st column is a row index, 0 if it's a column index.

The remove_indices variable is exactly identical to the remove_indices that you wrote in this comment, where each element correspond to an index into the colnames variable (which I should have named rowcolnames:

>> colnames'
ans =
  1×6 cell array
    {'R2'}    {'R3'}    {'R4'}    {'C4'}    {'C5'}    {'C6'}

so, [1;2;3] in remove_indices means remove R1, R2, R3 and [4;5;6] means remove C4, C5, C6. As I also wrote I believe the covers format is more useful.

[dpb]

"Your problem is a covering problem"

AH! Finally a recognition of what the OP wanted in a form I understand! :)

Congratulations and nice code/solution.

[NA]

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

[Guillaume]

"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]

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

[Guillaume]

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.