matlab: get all permutations for a specific logical matrix

Question

let's assume 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 single rows describe some objects identified by a certain attribute (e.g. balls of different colors) you could put into those baskets. 1 means, you can put it in (into the basket described by the column), 0 you can't.

Each basket can only contain ONE object at once. I'm wondering how to compute the permutations on how to put in objects for a given configurations, that means 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 possibilities:

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

so all in all, I have the complete permutations (one line describes one permutation, the column describe 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 this into a nice algorithm, which adapts to arbitrary number of baskets and objects? i can only think of nested and ugly looping :( thanks a lot!

Answer 1

You can use ndgrid. This function does 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 you complete question, you need to obtain [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 2

I would make 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 the output 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