Solved

Iterate through binary vector

Posted on 2008-10-19
8
708 Views
Last Modified: 2013-11-25
Hi,

I've got a binary vector N long and I want to be able to loop through all possible values of the vector and do some processing on it.
For example if N = 3;

001
Process
010
Process
100
Process
101
Process
011
Process
110
Process
111
Process

But would like to be able to do this in some sort of loop construction with N. So can then scale up to bigger sized vectors!

Any suggestions?
James
0
Comment
Question by:James_h1023
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
8 Comments
 
LVL 31

Expert Comment

by:Frosty555
ID: 22753387
I feel that a good direction to go with this is to instead use an N-dimensional matrix, instead of a single column vector filled with values. Fill each dimension of the matrix with alternating zeros and ones and then loop through each entry in the matrix in the correct way to iterate every possibility.

It would be easy to fill every alternative entry. To do it with a simple vector you can do something like:

x = zeros(50,1);
x(1:2:length(x)) = x(1:2:length(x)) + 1;

But I'm shaky on my matlab and I don't know if this is really the right way to do it. Some food for thought though.
0
 
LVL 4

Author Comment

by:James_h1023
ID: 22756146
Hi, thanks for a quick response.
Not quite sure I understand what your suggesting.
Can you clarify?

James
0
 
LVL 31

Expert Comment

by:Frosty555
ID: 22771904
Ah nevermind that's a stupid way of doing it. You only need a two dimensional matrix. What what I babbling about before?

You'll need to define a n by 2^n matrix using the zeros operator:

x = zeros(2^n, n);

Now, each row is a potential vector for you to analyze.

You need to fill in the columns following this pattern (for a 4-bit example)

0000
1000
0100
1100
0010
1010
0110
1110
0001
1001
0101
1101
0011
1011
0111
1111

Notice how the first column is just 0, 1, 0, 1. The second column is 0, 0, 1, 1, 0, 0, 1, 1. The third column is 0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1 etc. The number of consecutive numbers multiplies by two every time. What does this look like? It looks to me just like a square wave, or a clock signal.

The first column is just a clock signal with a period of 2
The second column is a clock signal with a period of 4
The third column is a clock signal with a period of 8
... etc.

You can also, conveniently, use matrix operations in MatLab to set the value of an entire column in one fell swoop, e.g.

x(:, 1) = [a clock signal with period 2]
x(:, 2) = [a clock signal with period 4]
x(:, 3) = [a clock signal with period 8]

etc.

All we need to do now is figure out how to synthesize that "clock signal" in matlab, which SURELY must be an easy thing to do. In fact, there's even a function called "square()" that is ALMOST what you want:

http://www.mathworks.com/access/helpdesk/help/toolbox/signal/index.html?/access/helpdesk/help/toolbox/signal/square.html

But it needs some tweaking to get anything other than a period of 2 to work. I'll keep hunting but this should put you on the right track. If you implement it this way, your function will not only be effective, and short, but also blazingly fast since you used almost entirely matrix operations to do it.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 4

Author Comment

by:James_h1023
ID: 22771918
Absolutely wonderful, I shall implement this when I have some time and have a look at the link :)

Thanks
0
 
LVL 31

Expert Comment

by:Frosty555
ID: 22771936
Now, the square function isn't quite right. It just generates 0,1,0,1,0,1. The period is 2. Always.

You'll run into trouble generating clock cycles with periods other than 2, but I'm sure there's some trickery you can do to puff out a matrix that looks like [0,1,0,1] into something like [0,0,0,1,1,1,0,0,0,1,1,1].
0
 
LVL 31

Accepted Solution

by:
Frosty555 earned 50 total points
ID: 22771998
Our only problem now is generating "clock" functions with period N. You might want to create a whole other matlab function to do just this, call it myclock() or something.

It might be possible to do it by creating an N by N matrix, the first row filled with all zeros, then the second filled with all ones, then all zeros etc. Then call "reshape" to turn that N x N matrix into an N² x 1 matrix.

E.g. create a matrix that looks like this:

0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1

Using subsequent calls to the zeros() and ones() function:

x = zeros(n,n)
x(1,:) = zeros(1,n)
x(2,:) = ones(2,n)
x(3,:) = zeros(3,n)
x(4,:) = ones(4,n)
.... etc up until column "n". Use a FOR loop to accomplish this.

And then call reshape() on that matrix:

e.g.
   reshape(x,[],1)

will result in a column vector:

0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1

wrap all that stuff into a function and use it to create the "clock" vectors we need for the first part of this problem.
0
 
LVL 15

Expert Comment

by:yuk99
ID: 23601292
I propose a solution using binary representation of integers. It works up to N=54, what will be 2^54-1 ~1.8e16 possible vectors.
You can get all the vectors with dec2bin(1:2^N-1)-48 (easy to get out of memory). 48 is ascii code for 0.

N=3;
for i=1:2^N-1
    dec2bin(i,N)-48
end

Open in new window

0
 

Expert Comment

by:WillDC
ID: 38967888
To create a matrix M of size R by C, with R indexed from zero to exp(2,C)-1, and which includes all possible binary vectors of size C, you can set M[r,c] equal to zero if ((r mod period(c)) < period(c)/2) evaluates to TRUE, and 1 otherwise. Period(c) is just 2 for the first column, 4 for the second, 8 for the third, 16, etc.
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

There is an easy way, in .NET, to centralize the treatment of all unexpected errors. First of all, instead of launching the application directly in a Form, you need first to write a Sub called Main, in a module. Then, set the Startup Object to th…
Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

733 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question