Matlab: get all permutations for a specific logical matrix

Question

Suppose I have the following logical matrix:

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

the columns describe something like a basket, and the individual lines describe some objects identified by a certain attribute (for example, balls of different colors) that you can put in these baskets. 1 means you can put it (in the basket described in the column), 0 you cannot.

Each basket can contain only one object. I am wondering how to calculate permutations in how to place objects for given configurations, which means that I say: I want to have objects in basket 1 and 3 but none in basket 2, which would be [1 0 1] :

So, I have the following options:

• basket 2: 0 items
• basket 1: may contain either object 1 or object. 3
• basket 3: may contain either object 2, obj. 3 or obj. 4

so overall, I have complete permutations (one row describes one permutation, the column describes the baskets, and the number describes the object):

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

how to make it a good algorithm that adapts to an arbitrary number of baskets and objects? I can only think of nested and ugly loops :( thanks a lot!

Answer 1

I would do it recursively:

 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 

gives a description that you describe:

 permlog(log,[1,0,1]) ans = 1 0 2 1 0 3 1 0 4 3 0 2 3 0 3 3 0 4 

Answer 2

You can use ndgrid . This function performs exactly what you are looking for.

 [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 

To answer the complete question, you need to get [1 2],[0],[2 3 4] from your log variable:

 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 

Answer 3

Found something in file sharing and now: http://www.mathworks.com/matlabcentral/fileexchange/10064-allcomb/content/allcomb.m This is a bit like Olis’s suggestion via ndgrid.