Compare each row of the matrix in Matlab with the rest

Question

I have a matrix Ain matlab of zeros and ones with dimension BxM.

In particular, it Acontains all possible arrangements of ones and zeros in spaces M, also taking into account the order (therefore, B=2^M).

• The matrix is ​​built so that for any i=1,...,N, A(i,:)>A(j,:)or A(i,:)><A(j,:)for j=i+1,...,N.
• Record A(i,:)>=A(j,:)means 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,...,Mwith severe inequality at least for one h.
• Writing A(i,:)><A(j,:)means it is not possible to establish whether A(i,:)>=A(j,:)or not .

For example, if 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);

A, A(i,:)>A(j,:) , B{i,j} A(k,:) , A(j,:)<A(k,:)<A(i,:).

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];

,

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

, M=20. , , , ?

, M=20 (2^20)x(2^20), , , .

, ( if ), . , , " " .

.

Answer 1

A ( " Matlab" ),

" ", A- . , . , .

,

A_by_row=@(rowIdx)(....)

, , parfor, GPU , .

:

ListIdx=0; 
for j=1:B 
 for h=1:B 
  if sum(A_by_row(j)==A_by_row(h))~=M, 
    ListIdx=ListIdx+1, 
    B_List(ListIdx).Coordinates=[j,h],     
    B_List(ListIdx).Result=**YourCodeThatMakesAnArbitraryLengthVec‌​tor**, 
  end, 
 end, 
end 

, .

.

Answer 2

, , , .

:

1) A "n" "n". : A (3) = [0,1,1]

2) A (j) A (h), A (j) A (h), .

3) M = 5 , , . : " ( (j), h) = (j, h) mod (2)"

4) .

function out = user3285148()
    M = 5;
    maxm = 2^M-1;
    for j = 0:maxm
        for h = 0:maxm;
            if predict(j,h)
                B{j+1,h+1} = [binaryarray(j,M);binaryarray(h,M)];
            end
        end
    end
    out  = B;
end

function out = binaryarray(in, length)
    out = zeros(1,length);
    bit = 0;
    while in>0;
        out(end-bit)=mod(in,2);
        in = floor(in/2);
        bit =bit+1;
    end
end

function out = predict(j,h)
    out =0;
    if h<j
        out = mod(nchoosek(j,h),2);
    end
end

B , (2 ^ 20) ^ 2 .

, , .

Answer 3

3.

• , B
• ( B)
• A ( B)

,

• : 1
• :

1

, j i > j , 0 j, 1 j 1 i. , , j

, hamming j , .

, j, 1 0.

, j. , j, .

j w, hamming d, nchoosek(w,d). , 2 M 2 w.

, n_j M x M, .

n_j = zeros(M);

for w=2:20
    for d=2:w
        n_j(w,d) = nchoosek(w,d);
    end
end 

, j .

, A, . nchoosek

n_i = zeros(M,1);

for w=2:M
    n_i(w) = nchoosek(M,w);
end

ij, j .

sum(n_i .* sum(n_j,2))

M = 20, 3.4753 e09. , . - 2 ^ 20 x 2 ^ 20, .

, . 2^d -2 , hamming , , , j.

n_j, , .

n_r = 2.^(1:M) - 2;

sum(sum((n_i*n_r).*n_j))

M = 20 1,0925 e12. , B 3.4753 e09 1.0925 e12, , .

---

2

, ij. , , i, j.

, A, , de2bi bi2de i A_row_i

A_row_i = de2bi(2^M - i, M)

i = 2^M - bi2de(A_row_i)

, i , , j .

w = sum(A_row_i);

j_s = n_j(w,:);

j_s M, , j .

, flips sum(j_s) x w 1 A_row_i A_row_j

flips=[];

for d=2:M
    c = nchoosek(1:w,d);
    out = ones(j_s(d),w);
    out(sub2ind([j_s(d),w],(1:j_s(d))'*ones(1,d),c))=0;
    flips = [flips;out];
end

, flips w, i, M-2 . .

, 1, A_row_i j

A_row_j = repmat(A_row_i,[sum(j_s),1]);
A_row_j(A_row_j==1) = flips;

j = 2^M - bi2de(A_row_j);

j j i.

1 2 ^ B, , M = 20, .

---

3

j, k . hamming d A_row_i A_row_j , flips, A_row_k k

- , A_row_i A_row_j , bitxor

A_row_i = de2bi(2^M - i, M);
A_row_j = de2bi(2^M - j, M);

d = pdist([A_row_i ; A_row_j],'cityblock');

flips = de2bi(1:2^d-2);

A_row_k = repmat(A_row_i,[n_r(d),1]);

flipable = repmat(bitxor(A_row_i,A_row_j),[n_r(d),1]);

A_row_k(flipable==1) = flips;

k = 2^M - bi2de(A_row_k);

B , j i, .

, , M = 20 .

Answer 4

!

:

Function out=A(row , number_of_bits)
        out=~bitget(row-1,number_of_bits:-1:1);
end

A(3,3)
ans =
     1     0     1 %which is identical with your A(3,:)

:

function [out]=B(n1,n2,number_of_bits)
   c1=A(n1,number_of_bits);
   c2=A(n2,number_of_bits);
   out=zeros(1,number_of_bits);
   out((c1==0)&(c2==1))=-1;
   if sum(out)>=0
      out=zeros(1,number_of_bits)+2;
      out(c1==0)=0;
      out(c2==1)=1; 
      out=int8(out);
   else
      out=[];
   end

%example:
B(1,4,3)
ans =
     1     2     2 %number 2 serves as wildcard ("*") and means that element could be either 0 or 1, you should discard A(1,:) and A(4,:) from the results so the actual size_of_B is (2^ number_of_wildcards)-2

:

B(1,1000000,20) 
ans =
  Columns 1 through 10
     2     2     2     2     1     2     1     1     1     1
  Columns 11 through 20
     2     1     1     1     2     2     2     2     2     2
  %which means that B(1,1000000) has (2^12)-2=4094 rows 

B(1,2,20)
ans =
  Columns 1 through 10
     1     1     1     1     1     1     1     1     1     1
  Columns 11 through 20
     1     1     1     1     1     1     1     1     1     2
  %which means that B(1,2) has (2^1)-2=0 rows 

size_of_B:

function out=size_of_B(b)
     if numel(b)==0
        out=0;
     else
        b(~(b==2))=0;
        b(~(b==0))=1;
        out=(2^sum(b))-2;
     end
%example:
size_of_B(B(1,1000000,20))
ans =
        4094

---

(2 ^ 19) * ((2 ^ 20) -1) ~ = 5e11 i, j for, : 1100 ! -B ( , B )

tic; 
 for i=1:1:10^9 
 end 
 toc
Elapsed time is 2.218067 seconds.
tic; 
 for i=1:1:10^10
 end 
 toc
Elapsed time is 22.165445 seconds.

---

%example:
 tic;
 M=10;
 n=1;
 for i=1:2^M
     for j=1:2^M
         if i<j
             c=B(i,j,M);
             if ~(size_of_B(c)==0)
                 d(n,:)=c;
                 n=n+1;
             end
         end
     end
 end
 toc
 [s,~]=size(d);
 s
Elapsed time is 10.095085 seconds. 
s =
          52905 %for M=10 there is 52905 pair of i,j with non-empty-B values;

M = 20 10 * 4 ^ 10 ~ = 10M ~ = 121 ! ( )

---

%script for plotting number of non-empty-B versus M
  d=[];
 for M=1:10
     tic;
     n=1;
     for i=1:2^M
         for j=1:2^M
             if i<j
                 c=B(i,j,M);
                 if ~(size_of_B(c)==0)
                     d(n,:)=c;
                     n=n+1;
                 end
             end
         end
     end
     toc
     [s,~]=size(d);
     d=[];
     h(M)=s;
 end
Elapsed time is 0.005418 seconds.
Elapsed time is 0.002238 seconds.
Elapsed time is 0.000933 seconds.
Elapsed time is 0.003058 seconds.
Elapsed time is 0.011650 seconds.
Elapsed time is 0.044217 seconds.
Elapsed time is 0.170286 seconds.
Elapsed time is 0.696161 seconds.
Elapsed time is 3.024212 seconds.
Elapsed time is 15.836280 seconds.
>> plot(h,'-o')

, , M = 20 ~ 3e9 B; (, , 20 ~ 60 B, , , , B )

Finally, I could mention that the exact number of non-empty-Bs can be calculated using a simple algorithm!