Binary matrix incrementer speed

Hello,

I need to do a brute-force simulation which has large (350x2688000) matrices.

for this, I built the following function in order to generate each possibility. But still, the code is too slow. I'm wondering if anybody could give me any hints in order to make them faster. The disp functions are only for testing

function increment (m,n)
  M=false(m,n);

    while max(max(M~=true(m,n)))
      if M==zeros
        Mmu=M;
        disp(M)
      end
      for a=1:m
          for b=1:n
            if a==1&&b==1&&M(a,b)
                M(a,b)=false;
            elseif a==1&&b==1&&~M(a,b)
                M(a,b)=true;
            elseif b==1&&~M(a-1,n)&&Mmu(a-1,n)&&~M(a,b)
                M(a,b)=true;
            elseif b==1&&~M(a-1,n)&&Mmu(a-1,n)&&M(a,b)
                M(a,b)=false;
            elseif b==1
                continue
            elseif ~M(a,b-1)&&Mmu(a,b-1)&&~M(a,b)
                M(a,b)=true;
            elseif ~M(a,b-1)&&Mmu(a,b-1)&&M(a,b)
                M(a,b)=false;
            end
          end

      end
      Mmu=M;
      disp(M)
    end

Thanks for your help!

--EDIT--

I dropped this way of coding due to the size of matrices involved, thanks anyway!

[per isakson]

What is this "max(max(M~=true(m,n)))"?

[Andrei Bobrov]

Hi Per!

This is (I mean): ~any(M(:))

[Vitor Frade]

Hey, actually it is ~all(M(:)), thanks, already reviewed.

[Matt Fig]

What are the m,n range you are interested in?

Answer 1

[Teja Muppirala]

You should be able to do it faster by calculating the matrices all at once and storing the result, instead of doing it one by one:

m = 2;
n = 3;

d = (0:(2^(m*n)-1));
M = rem(floor(pow2(0:-1:1-(m*n))'*d),2);
permute(reshape(M,n,m,[]),[2 1 3])

[Vitor Frade]

Hi, thanks for your help, that is how I started, the problem is that as d gets larger, it looses significance and doesn't output all matrices.

Answer 2

[Matt Fig]

You did not answer my question above, but here is another method. This produces the matrices in a different order than your code but much faster for, say m=n=5.

Note that this code uses npermutek, found on the FEX.

F = logical(npermutek([1 0],n));
G = npermutek(single(1:size(F,1)),m);

for ii = 1:2^(m*n) 
   M = F(G(ii,:),:);   % The M's you need
   disp(M)
end

[Vitor Frade]

Actually I was originally trying to use this algorithm as a brute force analysis matrix generator with m around 350 and n=268800, no matter how fast this code was, it would still take too long. I'm now looking into genetic algorithms to see if I can solve the problem (it's a schedule). thanks for the time you took helping me.

[Matt Fig]

Yes, 2^94080000 is a lot of matrices to generate! Good luck on your project.

[Teja Muppirala]

Vitor, do you realize that if m = 350 and n = 268800, the number of combinations is SOOOOO huge (2^(350*268800)) that it would be impossible to generate all of them, even with the fastest supercomputer in the world? In fact anything much greater than about m = 5 and n = 5, starts to get very large, very fast. If you are trying to generate possible solutions for a problem, you might want to take a look at another more tractable approach, for example, as you mention genetic algorithms.