Поиск подмножеств набора векторов, которые удовлетворяют некоторым условиям

Question

После всех отзывов, которые у меня были для этого вопроса, я внес изменения, чтобы сделать его более понятным и простым.

Для решения этой проблемы у меня есть матрица A и вектор строки A(1,2:7) (ссылка на строку), которая содержит как минимум один 0.

Из матрицы A:

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] 

Я хочу, чтобы найти один или, если возможно все комбинации векторов A(k,2:7),k≠1 and A(k,8)=0, в дополнение к A(1,2:7), которые удовлетворяют следующим условиям:

1. Комбинация формируется только с векторами, которые удовлетворяют A(k,8)=0; k=1,..,10

2. Я не буду рассматривать A (7,2: 7) в результатах, поскольку она не содержит 0.

3. если {A(1,2:7),A(j,2:7)} является данная комбинация, это означает, что на менее A(1,n)≠0 или A(j,n)≠0 для n = 2,...,7 , (По крайней мере, один из два значения, которые находятся на одной и той же колонке в A, должно быть отличается от 0)

4. Одна комбинация может содержать два или более векторов. Другой пример: , если {A(1,2:7),A(j,2:7),A(p,2:7)} представляет собой заданную комбинацию, это означает , что при менее A(1,n)≠0 или A(j,n)≠0 или A(p,n)≠0 для n = 2,...,7. (По крайней мере, одно из трех значений, которые находятся на одной и той же колонке в A, должна отличаться от 0)

5. Для матрицы A, {A(1,2:7),A(2,2:7)} представляет собой комбинацию, которая удовлетворяет желаемых условий. Но я не хочу иметь комбинацию , такую ​​как {A(1,2:7),A(2,2:7),A(3,2:7)}, так как A(1,2:7) и A(2,2:7) достаточны для формирования одной комбинации.

Для комбинации векторов, я должен взять один вектор в качестве эталона, в этом случае вектор A(1,2:7). Это вектор, который мы хотим компенсировать их нулями. Так A(1,2:7) способствует в ассоциации по его ненулевых компонент: 2,1 и 2.

, когда я говорю выше «Я хочу найти ... в дополнение к A(1,2:7)», это справедливо, когда A(1,2:7) является опорной строки. Но если A(5,2:7) является ссылкой на строку, в этом случае предложение становится «в дополнение к A(5,2:7)».

Для моей настоящей проблемы A является матрицей 700x8. Здесь A, A(1,2:7) и A(7,2:7) - всего лишь пример, я предпочитаю решение для любого вектора A(k,2:7) матрицы A, с A(k,8)=0 и, по крайней мере, одним из его компонентов является 0.

Answer 1

Вопрос немного сложный и неудобный. В любом случае я попытался написать код в меру моего понимания проблемы. Вот та часть, которая находит возможные комбинации:

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

Вот комбинации, которые я получил:

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

другими словами три комбинации; сначала с рядами [1 2], второй [1 5 8], и третий с рядами [1 5 9].

Часть, которую я оставил, является заключительным этапом вычисления «баллов» каждой найденной комбинации. Честно говоря, я не понимал, как это описание было непонятным! Поэтому я оставлю эту часть к вам ..

Answer 2

Если я правильно понял умопомрачительно усложненное описание требований, что было здесь, вы хотите:

• минимальный набор строк, включая один конкретная ссылка строки
• , которые все имеют в последнем столбце ноль, и по крайней мере один нуль в столбцах «данные»
• таким образом, что множество строк вместе содержат по крайней мере один ненулевой элемент в столбце каждые «данные»
  • и затем сделать некоторые пустячный о с полученными показателями

Поскольку я случайно провел последние пару дней работает на что-то подобное, это хорошо и свежо. Вот простой подход грубой силы: если эффективность с большими данными вызывает беспокойство, необходимо заменить все комбинации перед фронтом (я закончил писать рекурсивный итератор, который вызывает функцию обратного вызова для каждой комбинации, но я оставлю это для простоты здесь). Я предположил, что первый столбец всегда будет содержать соответствующие исходные индексы в соответствии с примером - это позволяет легко разделить данные без потери следа, а разделение данных помогает немного упростить логику.

Пример настройки:

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]; 
% data columns 
colidx = 2:7; 
% reference row 
refidx = 1; 
indices = findindices(A, refidx, colidx) 
% then muck about with the indices as need be 

Функции:

function indices = findindices(A, refidx, colidx) 
% pick out the relevant rows 
setidx = (A(:,8) == 0) & ~all(A(:,colidx), 2) & (A(:,1) ~= refidx); 
ref = A(refidx, :); 
rows = A(setidx, :); 
% no need to pass any more than the columns of interest here 
c = findcombination(ref(colidx), rows(:,colidx)); 
% turn the combination of 'rows' indices back into the original ones, 
indices = [ref(1); rows(c, 1)]; 
end 

function c = findcombination(ref, rows) 
n = size(rows, 1); 
% search all 1-combinations first, then 2-combinations, etc. 
% to ensure we find the smallest first. 
for k=1:n 
    for c = nchoosek(1:n, k)' 
     set = [ref; rows(c,:)]; 
     if any(set, 1) % true if all columns have at least one nonzero 
      return; % c contains the combination in terms of the rows array 
     end 
    end 
end 
c = []; 
error('no valid combination!') 
end 

И результат для примера данных:

>> test 

indices = 

    1 
    2