Binary matrix incrementer speed

2012 8 13
2 个回答
4 次查看（30 天）

0 个投票

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更早的评论 隐藏 2更早的评论

per isakson
per isakson 2012-8-13
What is this "max(max(M~=true(m,n)))"?
Andrei Bobrov
Andrei Bobrov 2012-8-13
编辑：Andrei Bobrov 2012-8-13
Hi Per!
This is (I mean): ~any(M(:))
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

2 个投票

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 个评论
显示 -1更早的评论 隐藏 -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

1 个投票

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更早的评论 隐藏 1更早的评论

Vitor Frade
Vitor Frade 2012-8-13
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
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.

请先登录，再进行评论。

类别

在 帮助中心 和 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