Compare each row of a matrix with the remaining ones

1 view (last 30 days)
MRC
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.

Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by