Identify the minimum number of rows in a matrix meeting a condition

Hi everyone,

Please assume that I have a matrix as follows:

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

I would like to identify and selcet the minimum number of rows that have value of one in all columns (altoghether). For example, rows 2 and 5 are the best choice for matrix A. Do you have any suggestion?

Regards,

Amir

[Matt J]

What about this case?

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

You could argue that A([1,3],:) is the minimal selection because only those two rows contain a cluster of two [1,1] whereas all three rows contain the single-element cluster [1], possibly as sub-clusters of the [1,1] sequences.

On the other hand, if you make the rule that a cluster of length n cannot belong to a longer cluster of length m>n and can therefore be neighbored only by zeros, then A(2,:) is the minimal selection because now it is the only row qualifying as having a single-element cluster [1].

[Amirhossein Moosavi]

I am not sure if I have understood completely.

Answer 1

[Matt J]

This solution uses the Optimization Toolbox, although I am still only half certain what row-selection rule you are looking for (see my question here).

 [m,n]=size(A);
 
 irp=1:m;
 rp=randperm(m); %row permutation
 irp(rp)=irp;    %inverse permutation
 
 Ap=A(rp,:);

 x=optimvar('x',[1,m],'LowerBound',0,'UpperBound',1,'Type','integer');
 
 prob=optimproblem('Objective',sum(x));
 prob.Constraints=(x*Ap>=ones(1,n));
 
  sol=solve(prob);

  selection=find(round(sol.x(irp)));

[Amirhossein Moosavi]

Yes, it seems to be a solution. However, there are two problems:

1) It is not fast.

2) It is baised toward one combination when multiple combinations meet the condition. For example, see the below matrix:

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

[Matt J]

2) Just randomly pre-permute the rows of A (see my edited version above).

1) I find that my version is faster than yours for larger problems even when adding in the above permutation. For example, with A = randi([0,1],40,100), I find

Elapsed time is 0.193646 seconds.%Matt J
Elapsed time is 0.367822 seconds.%Amir

Answer 2

[madhan ravi]

According to what I understood, see if this does what you want to do:

 [a, b] = unique(A, 'rows', 'stable');
 s = sum(a, 2);
 rows = b(s > 1)

[Amirhossein Moosavi]

Thanks! Unfortunately, this is not a solution for my quesiton. You would follow my above examples (1 and 2) for further clarification. If you still need more explanation, please let me know.

Answer 3

[Amirhossein Moosavi]

This is a code that addresses my question, but I am not sure whether it is the fastest way or not.

EG = cell(1, 100); % A place to store eligible combinations

cn1 = 1; cn2 = 1; FG = 0;
for i = 1:size(A, 2)
    
    C = nchoosek(1:size(A, 1), cn1); % A function to create all combinations of rows (starting from the minimum number)
    for j = 1:size(C, 1)
        S = sum(A(C(j, :), :));
        
        if all(S >= 1) && (sum(S) >= size(A, 2)) % The condition that I explained in my question
            EG{cn2} = C(j, :);
            cn2 = cn2 + 1;
            FG = 1;
        end
    end
    
    if FG == 1 % If at least one combination has been found, break the loop (no need to check combinations with more number of rows)
        break;
    end
    
    cn1 = cn1 + 1;
end

EG(cn2:end) = []; 
selection = EG{randi([1 numel(EG)])}; % Randomly select one of the eligible combinations

Do you have any suggestion to make it faster?

[Matt J]

My method is faster for larger problems. For this matrix,

A = randi([0,1],40,100);

I obtain these timings,

Elapsed time is 0.193646 seconds.%Matt J
Elapsed time is 0.367822 seconds.%Amir

[Amirhossein Moosavi]

Thank you so much for your kind help!