Quick way of finding complementary vectors in MATLAB

Question

I have a matrix of N rows of binary vectors, i.e.

mymatrix = [ 1 0 0 1 0;
             1 1 0 0 1;
             0 1 1 0 1;
             0 1 0 0 1;
             0 0 1 0 0;
             0 0 1 1 0;
             ....       ]

where I'd like to find the combinations of rows that, when added together, gets me exactly:

[1 1 1 1 1]

So in the above example, the combinations that would work are 1/3, 1/4/5, and 2/6.

The code I have for this right now is:

i = 1;
for j = 1:5
    C = combnk([1:N],j); % Get every possible combination of rows
    for c = 1:size(C,1)
        if isequal(ones(1,5),sum(mymatrix(C(c,:),:)))
            combis{i} = C(c,:);
            i = i+1;
        end
    end
end

But as you would imagine, this takes a while, especially because of that combnk in there.

What might be a useful algorithm/function that can help me speed this up?

Answer 1

M = [
 1 0 0 1 0;
 1 1 0 0 1;
 0 1 1 0 1;
 0 1 0 0 1;
 0 0 1 0 0;
 0 0 1 1 0;
 1 1 1 1 1
];

% Find all the unique combinations of rows...
S = (dec2bin(1:2^size(M,1)-1) == '1');

% Find the matching combinations...
matches = cell(0,1);

for i = 1:size(S,1)
    S_curr = S(i,:);
    
    rows = M(S_curr,:);
    rows_sum = sum(rows,1);
    
    if (all(rows_sum == 1))
        matches = [matches; {find(S_curr)}];
    end
end

To display your matches in a good stylized way:

for i = 1:numel(matches)
    match = matches{i};
    
    if (numel(match) == 1)
        disp(['Match found for row: ' mat2str(match) '.']);
    else
        disp(['Match found for rows: ' mat2str(match) '.']);
    end
end

This will produce:

Match found for row: 7.

Match found for rows: [2 6].

Match found for rows: [1 4 5].

Match found for rows: [1 3].

In terms of efficiency, in my machine this algoritm is completing the detection of matches in about 2 milliseconds.