Compare each row of a matrix with the remaining ones

Question

MRC 2017-3-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/331490-compare-each-row-of-a-matrix-with-the-remaining-ones

编辑： MRC 2017-3-23

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 0;
0 1;
0 0;
1 1;
1 0;
0 1
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.