# Compare each row of a matrix with the remaining ones

2 views (last 30 days)
MRC on 23 Mar 2017
Edited: MRC on 23 Mar 2017
I have a matrix A of zeros and ones with dimension BxM.
Specifically, A contains all the possible dispositions of ones and zeros in M spaces considering also the order (hence, B=2^M).
• The matrix is built such that, for any i=1,...,N, A(i,:)>A(j,:) or A(i,:)><A(j,:) for j=i+1,...,N.
• Writing A(i,:)>=A(j,:) means that A(i,h)>=A(j,h) for h=1,...,M.
• Writing A(i,:)>A(j,:) means that A(i,h)>=A(j,h) for h=1,...,M, with strict inequality for at least one h.
• Writing A(i,:)><A(j,:) means that it is not possible to establish whether A(i,:)>=A(j,:) or viceversa.
For example when M=3
A=[1 1 1;
1 1 0;
1 0 1;
1 0 0;
0 1 1;
0 1 0;
0 0 1
0 0 0];
Consider
B=cell(2^M, 2^M);
For ANY two comparable rows of A, A(i,:)>A(j,:), I want B(i,j) containing all rows A(k,:) such that A(j,:)<A(k,:)<A(i,:).
In the example above, the desired output would be
B{1,4}=[1 1 0; 1 0 1];
B{1,6}=[1 1 0; 0 1 1];
B{1,7}=[1 0 1; 0 1 1];
B{1,8}=[1 1 0; 1 0 1; 1 0 0; 0 1 1; 0 1 0; 0 0 1];
B{2,8}=[1 0 0; 0 1 0];
B{3,8}=[1 0 0; 0 0 1];
B{5,8}=[0 0 1; 0 1 0];
This code does what I want
B=cell(2^M, 2^M);
for j=1:size(A,1)
for h=1:size(A,1)
if sum(A(j,:)==A(h,:))~=M && sum(A(j,:)>=A(h,:))==M %if A(j,:)>A(h,:) according to the meaning indicated above
B{j,h}=A(any(bsxfun(@ne, A,A(j,:)),2) & any(bsxfun(@ne, A,A(h,:)),2) &...
all((bsxfun(@le, A,A(j,:)) & bsxfun(@ge, A,A(h,:))),2),:);
end
end
end
However, the code above is not feasible because in my actual case M=20. Do you have suggestions on whether it is possible to speed it up and, if yes, how?
One of the main problems of the code is that, for M=20, it requires to preallocate a cell (2^20)x(2^20) which, clearly, cannot be done. On the other hand, at the end of the double loop, lots of cells are empty and what I really need is to keep tracks of the content and of the coordinates only of the non-empty ones. Hence, maybe, a "sparse cell" could help me here.
Any suggestion would be really appreciated.