Matlab: получить все перестановки для конкретной логической матрицы - PullRequest
Новая
       6

Matlab: получить все перестановки для конкретной логической матрицы

4 голосов
/ 29 февраля 2012

давайте предположим, что у меня есть следующая логическая матрица: 

log = [1 1 0; 
       0 1 1; 
       1 0 1; 
       0 0 1];

столбцы описывают что-то вроде корзины, а одиночные строки описывают некоторые объекты, идентифицируемые определенным атрибутом (например, шары разных цветов), которые вы можете поместить в эти корзины. 1 означает, что вы можете положить его (в корзину, указанную в колонке), 0 вы не можете.

Каждая корзина может содержать только ОДИН объект одновременно. Мне интересно, как вычислить перестановки о том, как вставить объекты для заданных конфигураций, это означает, что я говорю: I want to have objects in basket 1 and 3 but none in basket 2, which would be [1 0 1]:

Итак, у меня есть следующие возможности:

  • корзина 2: 0 товаров
  • корзина 1: может содержать объект 1 или объект. 3
  • корзина 3: может содержать любой объект 2, объект. 3 или объект 4

итак, у меня есть полные перестановки (одна строка описывает одну перестановку, столбец описывает корзины, а число описывает объект): 

1 0 2
1 0 3
1 0 4
2 0 2
2 0 3
2 0 4

как превратить это в хороший алгоритм, который адаптируется к произвольному количеству корзин и объектов? я могу думать только о вложенных и некрасивых циклах :( Большое спасибо!

Ответы [ 3 ]

5 голосов
/ 29 февраля 2012

Вы можете использовать ndgrid.Эта функция делает именно то, что вы ищете. 

[b1 b2 b3]=ndgrid([1 2],[0],[2 3 4]);
[b1(:) b2(:) b3(:)]

ans =

 1     0     2
 2     0     2
 1     0     3
 2     0     3
 1     0     4
 2     0     4

Чтобы ответить на ваш полный вопрос, вам нужно получить [1 2],[0],[2 3 4] из лог-переменной: 

log = [1 1 0; 
   0 1 1; 
   1 0 1; 
   0 0 1];
 log=bsxfun(@times,log,[1 0 1]);
 poss=cellfun(@find,mat2cell(log,size(log,1),ones(1,size(log,2))),'UniformOutput',0)
 poss(cellfun(@isempty,poss))={0}
 basket=cell(1,size(log,2));
 [basket{:}]=ndgrid(poss{:});
 basket=cell2mat(cellfun(@(x) x(:),basket,'UniformOutput',0))

basket = 

 1     0     2
 3     0     2
 1     0     3
 3     0     3
 1     0     4
 3     0     4
4 голосов
/ 29 февраля 2012

Я бы сделал это рекурсивно: 

function out = permlog(log,bag)
if bag(1)==0
    curr=0;
else
    curr = find(log(:,1));
end
if size(log,2)==1
    out = curr;
    return
else
    add = permlog(log(:,2:end),bag(2:end));
    out = [];
    for i=1:numel(curr)
        tmp = [repmat(curr(i),size(add,1),1),add];
        out =[out;tmp];
    end
end

дает вывод, который вы описываете: 

permlog(log,[1,0,1])

ans =

     1     0     2
     1     0     3
     1     0     4
     3     0     2
     3     0     3
     3     0     4
0 голосов
/ 07 марта 2012

Теперь нашел что-то в обмене файлами: http://www.mathworks.com/matlabcentral/fileexchange/10064-allcomb/content/allcomb.m Это немного похоже на предложение Олиса через ndgrid.

...