[Solved] Finding subsets of a set of vectors that fulfill some conditions

by


The question is a bit complicated and hard to follow.. Anyways I tried writing some code to the best of my understanding of the problem. Here is the part that finds the possible combinations:

% input matrix
A=[1   2 0 1 2 0 0   0
   2   1 1 1 0 2 2   0
   3   0 0 0 0 1 1   1
   4   0 2 0 1 1 1   2
   5   0 0 0 0 0 1   0
   6   1 0 1 1 2 0   2
   7   1 1 2 2 2 1   1
   8   0 1 1 2 2 0   0
   9   0 1 1 2 2 0   0
  10   2 2 2 2 0 0   1];

% start by considering all rows
rowsIndices = (1:size(A,1))';
rIdx = true(size(rowsIndices));

% exclude 7th row (i.e rows with no zeros in columns 2:7)
%idx(~any(A(:,2:7)==0,2)) = false;
rIdx(7) = false;

% exclude rows that dont have zero in column 8
rIdx(A(:,8) ~= 0) = false;

% for each possible n-combinations
N = sum(rIdx);
combs = cell(1,N);
for k=2:N
    % all combinations of k-rows
    combsK = nchoosek(rowsIndices(rIdx), k);

    % must involve first row
    combsK = combsK(any(combsK==1,2),:);

    % exclude from current k-combinations if there are smaller ones
    if k > 2
        combsKIdx = true(size(combsK,1),1);
        for kk=2:k-1
            if isempty(combs{kk}), continue, end
            for i=1:size(combs{kk},1)
                combsKIdx(sum(ismember(combsK,combs{kk}(i,:)),2)==kk) = false;
            end
        end
        combsK = combsK(combsKIdx,:);
    end

    % for every possible combination, each column 2:7 must not be all zeros
    combsKIdx = true(size(combsK,1),1);
    for i=1:size(combsK,1)
        combsKIdx(i) = all(any(A(combsK(i,:),2:7),1));
    end
    combsK = combsK(combsKIdx,:);

    % store combinations found
    combs{k} = combsK;
end

% display results
celldisp(combs)

Here are the combinations I got:

combs{1} =
     []
combs{2} =
     1     2
combs{3} =
     1     5     8
     1     5     9
combs{4} =
     []
combs{5} =
     []

in other words three combinations; first with rows [1 2], second [1 5 8], and third with rows [1 5 9].

The part I left out is the final step of computing the “scores” of each combination found. Honestly I didn’t understand how, the description was confusing! So I’ll leave that part to you..

7

solved Finding subsets of a set of vectors that fulfill some conditions