Binary matrix incrementer speed

19 次查看（过去 30 天）
Vitor Frade
Vitor Frade 2012-8-13
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!
  4 个评论
显示 2更早的评论
Vitor Frade
Vitor Frade 2012-8-13
Hey, actually it is ~all(M(:)), thanks, already reviewed.
Matt Fig
Matt Fig 2012-8-13
What are the m,n range you are interested in?

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

Teja Muppirala
Teja Muppirala 2012-8-13
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])
  1 个评论
Vitor Frade
Vitor Frade 2012-8-13
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.

请先登录，再进行评论。

Matt Fig
Matt Fig 2012-8-13
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
  3 个评论
显示 1更早的评论
Matt Fig
Matt Fig 2012-8-13
Yes, 2^94080000 is a lot of matrices to generate! Good luck on your project.
Teja Muppirala
Teja Muppirala 2012-8-13
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Matrix Computations 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by