Nested For Loops

From CDS 130

Jump to: navigation, search

Contents

  1. Objective
  2. Motivation
  3. Priming question
  4. Notes
    1. Nested objects
    2. Introduction
    3. Introduction cont.
    4. Introduction cont.
    5. Populate a Matrix
    6. Evaluation of a nested for loop
    7. Evaluation of a nested for loop
    8. Question
    9. Question
    10. Question
    11. Answer
  5. Questions
    1. Short-hand to long-hand I
    2. Short-hand to long-hand II
    3. Interpreting a loop I
    4. Interpreting a loop II
    5. Interpreting a loop III
    6. Interpreting a loop 0100
    7. Interpreting a Loop V
    8. Read a nested loop
    9. Write a nested loop
    10. Filling a matrix
    11. Triple for loop I
    12. Triple for loop II
  6. Tutorial
  7. Resources

1. Objective

  • To introduce nested for loops.

2. Motivation

  • Before we can handle images, we need to be able to manipulate matrices.
  • Nested for loops is the most basic way a matrix can be manipulated.

3. Priming question

  • What is confusing about for loops?

4. Notes

4.1. Nested objects

From static.dezeen.com on June 25 2017 11:10:30.

4.2. Introduction

  • A for loop does this
c = 0;
for i = [1:3]

  Do something

end
  • Do something can be another for loop:
for j = [1:2]
  c = c+1;   
end
  • Putting the two together gives
c = 0;
for i = [1:3]

  for j = [1:2]
    c = c+1; 
  end

end

4.3. Introduction cont.

The first step in working out what happens is to expand the inner for loop:

c = 0;
for i = [1:3]

   j = 1;
     c = c+1;
   j = 2;
     c = c+1; 

end

4.4. Introduction cont.

The second step is to expand the outer loop. In this case, a set of four command will be repeated three times:

 c = 0;
 i = 1;
   j = 1;
     c = c+1; % c = 0 + 1 = 1;
   j = 2;
     c = c+1; % c = 1 + 1 = 2;
 i = 2;
   j = 1;
     c = c+1; % c = 2 + 1 = 3;
   j = 2;
     c = c+1; % c = 3 + 1 = 4;
 i = 3;
   j = 1;
     c = c+1; % c = 4 + 1 = 5;
   j = 2;
     c = c+1; % c = 5 + 1 = 6;

4.5. Populate a Matrix

A nested for loop can be used to populate a matrix:

  • A for loop does this
for i = [1:3]

  Do something

end
  • Do something can be another for loop:
for j = [1:2]
  B(i,j) = 1.0   
end
  • Putting the two together gives
for i = [1:3]

  for j = [1:2]
    B(i,j) = 1.0   
  end

end

4.6. Evaluation of a nested for loop

  • Re-write the original program long-hand form in two steps. First re-write the inner for loop as long-hand and leave the outer loop. Then re-write the outer part in long-hand form.
  • What will the matrix B look like after you run the program?
  • Original program


for i = [1:3]

  for j = [1:2]
    B(i,j) = 1.0   
  end

end
  • Step 1: Fill in the space below with the long-hand version of the inner for loop.
for i = [1:3]








 


end
  • Step 2: Fill in the space below with the long-hand version of what you wrote for step 2.






4.7. Evaluation of a nested for loop

  • Re-write the original program long-hand form in two steps. First re-write the inner for loop as long-hand and leave the outer loop. Then re-write the outer part in long-hand form.
  • What will the matrix B look like after you run the program?
  • Original program


for i = [1:3]

  for j = [1:2]
    B(i,j) = 1.0   
  end

end
  • Step 1: Fill in the space below with the long-hand version of the inner for loop.
for i = [1:3]

  j = 1;
    B(i,j) = 1.0;
  j = 2;
    B(i,j) = 1.0;
 
end
  • Step 2: Fill in the space below with the long-hand version of what you wrote for step 2.
i = 1;
  j = 1;
    B(i,j) = 1.0;
  j = 2;
    B(i,j) = 1.0; 
i = 2;
  j = 1;
    B(i,j) = 1.0;
  j = 2;
    B(i,j) = 1.0;
i = 3;
  j = 1;
    B(i,j) = 1.0;
  j = 2;
    B(i,j) = 1.0;   

4.8. Question

What is B? Do it by hand and then enter into MATLAB. Important: Write out long-hand version on paper first!

for i = [1:2]
   for j = [1:2]
     B(i,j) = i+j;
   end
 end


4.9. Question

What is B? Do it by hand and then enter into MATLAB.

clear B;
B(1,1) = 13.0;
for i = [2:3]
   for j = [2:3]
     B(i,j) = i+j;
   end
 end


4.10. Question

  • Previously we discussed how a matrix could be created with this notation, which "stacks" the row of numbers 1 2 3 on top of the row of numbers 4 5 6.
A = [1,2,3 ; 4,5,6 ]
  • Matrices can be "stacked" too
B = [A ; A]

or

A = [A ; A]

what is the difference between the above two options?

  • Predict what will happen when this program is run
clear
A = [1,2,3 ; 4,5,6]
for i = [1:3]
  A = [A ; A]
end


4.11. Answer

  • After iteration 1
A =

   1   2   3
   4   5   6
   1   2   3
   4   5   6
  • After iteration 2
A =

   1   2   3
   4   5   6
   1   2   3
   4   5   6
   1   2   3
   4   5   6
   1   2   3
   4   5   6
  • After iteration 3
A =

  1   2   3
  4   5   6
  1   2   3
  4   5   6
  1   2   3
  4   5   6
  1   2   3
  4   5   6
  1   2   3
  4   5   6
  1   2   3
  4   5   6
  1   2   3
  4   5   6
  1   2   3
  4   5   6

5. Questions

These questions are intended to be worked in order, as each question builds on the previous question. To answer these questions, please refer to Nested_For_Loops#Slides, your notes from class, and Nested_For_Loops#Tutorial.

5.1. Short-hand to long-hand I

  • Re-write the nested for loop program given below in long-hand form in two steps. First re-write the inner for loop in long-hand and leave the outer loop. Then re-write the outer part in long-hand form.
  • What will the matrix B look like after you run the program?
  • Original program
c = 10;
for i = [1:2]

  for j = [3:4]
    c = c + 2.0;  
  end

end
  • Step 1: Fill in the space below with the long-hand version of the inner for loop.
for i = [1:2]








end
  • Step 2: Fill in the space below with the long-hand version of what you wrote for step 2. Check your answer by running your program to see if you get the same matrix B as that when running the original nested for loop program.

5.2. Short-hand to long-hand II

  • Re-write the nested for loop program given below in long-hand form in two steps. First re-write the inner for loop in long-hand and leave the outer loop. Then re-write the outer part in long-hand form.
  • What will the matrix B look like after you run the program?
  • Original program


for i = [2:3]

  for j = [1:2]
    B(i,j) = 1.0   
  end

end
  • Step 1: Fill in the space below with the long-hand version of the inner for loop.
for i = [2:3]









end
  • Step 2: Fill in the space below with the long-hand version of what you wrote for step 2. Check your answer by running your program to see if you get the same matrix B as that when running the original nested for loop program.

5.3. Interpreting a loop I

Which set of nested for loops will produce the matrix M?

  • A.
  • B.
  • C.
  • D.
  • All of the above.
  • None of the above.
M = 
    1 2 3
    4 5 6
    7 8 9

A.

for j = [1:3]
  for i = [1:3]
    M(i,j) = i+j;
  end
 end

B.

for i = [1:3]
  for j = [1:3]
    M(i,j) = i-j;
  end
 end

C.

for i = [1:3]
  for j = [1:3]
    M(i,j) = i
  end
 end

D.

for i = [1:3]
  for j = [1:3]
    M(i,j) = i*j
  end
 end


5.4. Interpreting a loop II

Which matrix will result from evaluating the nested for loop below?

  • A.
  • B.
  • C.
  • D.
  • All of the above.
  • None of the above.
counter = 1;
for j = [1:3]
  for i = [1:3]
    M(i,j) = counter;
    counter = counter + 1;
  end
 end

A.

M = 
   1 1 1
   2 2 2
   3 3 3

B.

M = 
   1 2 3
   4 5 6
   7 8 9

C.

M = 
   1 4 7
   2 5 8
   3 6 9

D.

M = 
   9 6 3
   8 5 2
   7 4 1


5.5. Interpreting a loop III

Which matrix will result from evaluating the nested for loop below?

  • A.
  • B.
  • C.
  • D.
  • All of the above.
  • None of the above.
clear M;
counter = 1;
for j = [1:3]
  for i = [1:3]
    M(i,j) = i+j;
    counter = counter+1;
  end
 end

A.

M = 
   1 4 7
   2 5 8
   3 6 9

B.

M =

  1 2 3
  2 4 6
  3 6 9

C.

M = 
   9 6 3
   8 5 2
   7 4 1

D.

M = 
   2 3 4
   3 4 5
   4 5 6


5.6. Interpreting a loop 0100

Which matrix will result from evaluating the nested for loop below?

  • A.
  • B.
  • C.
  • D.
  • All of the above.
  • None of the above.
clear M;
counter = 1;
for j = [1:3]
  for i = [1:3]
    M(i,j) = counter+j;
    counter = counter+1;
  end
 end

A.

M = 
   1 4 7
   2 5 8
   3 6 9

B.

M =
  1 2 3
  2 4 6
  3 6 9

C.

M =
   2 6 10
   3 7 11
   4 8 12

D.

M = 
   2 3 4
   3 4 5
   4 5 6


5.7. Interpreting a Loop V

What are the values in the matrix M after executing this program?

for j = [-1:1]
  for i = [0:1]
    M(i+1,j+2) = j;
  end
 end
 M


5.8. Read a nested loop

Consider the following MATLAB code:

for i=[1:40]
   for j=[1:40]
      M(i,j) = (i-3)*(j+3);
   end
end

When the above code is run, what are the values in the following locations of the M array?

M(10,15)
M(12,32)
M(20,21)
M(35,1)
M(40,27)

5.9. Write a nested loop

Create a file called nested.m and enter the commands from the previous problem in it. Below these commands, write a nested for loop that prints out the first five values from rows 22, 23 and 24 of M. Execute the commands by typing nested on the command line. On the sheet that you turn in, write out your code and the output from running it.

5.10. Filling a matrix

There is one row of the matrix M that results when entering the commands

clear M
M(2,4) = 10.0

that is filled completely with zeros (that is, the value 0 is stored at all locations in that specific row). Which row is it, and why does each location in this row contain the value zero? (The command clear M deletes any previously defined matrix M.


Write MATLAB code to fill all positions of the row in M that you identified in the previous problem with the new value 4.5. Ensure that only the values in this particular row are assigned the new value 4.5. Run your program to verify that positions in this particular row of M now contain the value 4.5 and not 0. Show both your Matlab/Octave program and the output from running your it. (Note: When solving this problem, you will need only one for loop.


5.11. Triple for loop I

When the following is executed, describe what will be shown on the screen. (Note that the line counter = counter + 1 does not have a semi-colon a the end.)

counter = 1;
for i = [1:32]
  for j = [1:32]
    for k = [1:2]
      counter = counter + 1
    end
  end
end



5.12. Triple for loop II

When the following is executed, describe what will be shown on the screen. (Note that the line counter = counter + 1 does not have a semi-colon at the end.)

counter = 1;
for i = [1:10]
  for j = [1:10]
    for k = [1:10]
      counter = counter + 1
    end
  end
end


6. Tutorial

By Joseph Marr (Slight modifications by Robert Weigel - Original version)

This is a short tutorial on the concept of nested FOR loops, which will be useful for you when we consider image processing. The concept is not difficult, but it involves a bit more "bookkeeping" because now we have two FOR loops executing together, instead of just one FOR loop executing by itself. Furthermore, one of these loops will be INSIDE the other loop, and thus, executes all the way through (i.e., executes fully) for EACH iteration of the outer FOR loop. We'll begin with a simple example and build this example up toward the nested FOR loop structure.

First consider the standard FOR loop that we already know:

for i=[1:5]
  A(i) = i;
end

If we run this code, we will create an array called "A" and fill each of its five positions (1--5) with a value. That value will be an integer corresponding to the array position: A(1) = 1, A(2) = 2, A(3) = 3, A(4) = 4, and A(5) = 5. Recall that we don't see these values printed to the screen because I intentionally ended the assignment statement with a semi-colon, which as we know suppresses output. But, the A array is still in memory, waiting to be used (in Matlab, look in the upper right hand corner of the screen, in the area called "Workspace", and you'll see a small yellow icon there with the name A attached---thus, array A is indeed in memory). If, in a later calculation, we wanted to use the entire array A, we would simply type "A" into a calculation that accepts an array as input, and that calculation would be performed on each element of array A, simultaneously (most arithmetic calculations behave like this, but a few of them require slight modification). Thus, if I wanted to add the integer 5 to each of the elements of array A, and assign the result to an array called "B", I would write the following Matlab statement:

B = A+5

Note that I didn't need to ask for explicit positions like A(1), A(2), etc., to do the addition. Rather, the addition was done "all at once", on the entire array A, with Matlab taking care of the details for us. Of course, we could have done the same thing by adding the integer 5 to each element of A, one at a time, and assigning the result to an array B, like this:

for i=[1:5]
  B(i) = A(i)+5;
end

This accomplishes the same objective.

You might therefore ask why we would EVER consider writing a FOR loop to do an element-by-element addition like this, when one simple statement, namely, , does the job just fine. We wouldn't---in Matlab! But OTHER computer languages don't take care of all the details for you like Matlab does, so it's good to know how to do the addition element by element.

But, there's more...

One might ALSO want to perform mathematical operations (possibly different) on each of the elements of array A, or to inspect each element of A and perhaps make some sort of decision based on what one finds. That's more sophisticated than just adding the integer 5 to each element of an array. And so, doing sophisticated things may require us to look at each element of an array, one by one. That's a good reason why we need to know how to access array elements one at a time, as shown above.

So far, we've been working with one dimensional arrays, that is, a long string of numbers all lined up in a row. That's what the A and B arrays above are--one dimensional arrays. Long strings of numbers. But arrays can be constructed that have more than just one dimension.

The most common type of array in computational science is the two dimensional array. Whereas one dimensional arrays can be thought of as a single row of boxes (each box containing a value), two dimensional arrays can be thought of as a "square filled with boxes". Here's a standard one dimensional array, the A array from above, holding the values we assigned to it with the first FOR loop above:

[1,2,3,4,5]

And now, here's a two dimensional array, which as you can see in this particular case, holds a lot more values:

 1  2  3  4   5
 6  7  8  9  10
11 12 13 14  15
16 17 18 19  20
21 22 23 24  25

The one dimensional array A is known as a "one-by-five" array, or "1x5". This means that there's one row and five columns. The two dimensional array, on the other hand, is known (in this particular case) as a "five-by-five" array, or "5x5". This means that there are five rows and five columns.

Now in the above Matlab code we accessed locations inside A using a single variable---in this case, the letter "i" which the FOR loop assigns the successive values 1, 2, 3, 4 and 5. If later we want to know what value is located in, say, the third location inside A, I simply write "A(3)" and Matlab responds (in this case) with the integer 3:

A(3)
ans =
  3

Of course, I can use values from any A array location. All I need to do to retrieve the value from a specific A location, is write the name of the array, followed by a left parenthesis, followed by the position number in the array (which has stored in it the value I am seeking), followed by a right parenthesis. Of course, you've been doing this all along in your own Matlab/Octave programs when you wrote statements such as:

A(i+1)=A(i)+0.05*A(i)

When you wrote statements like that, you accessed SPECIFIC array locations, and then, used the values stored in these locations for subsequent computations. The variables "i", "j" and "k" are commonly used in programming to indicate specific array locations. When "i" (or any other variable for that matter) is used in this manner, it is called an "array index variable", or an "array index", or simply an "index". In the examples we've been discussing, "i" has been our array index.

The situation is analogous for two dimensional arrays, but in that case, we vary two variables rather than just one. A square is two dimensional, having a length and a width. Likewise, a two dimensional array has one index for its rows, and another for its columns. Consider the 3x3 array "C". C, being a 3x3 array, has values stored in the following locations: C(1,1), C(1,2), C(1,3), C(2,1), C(2,2), C(2,3), C(3,1), C(3,2) and C(3,3). We will need to use two index variables instead of one to access these C locations because we can make row and column choices independently if we wish. If we let each row be referenced by index variable "i" and each column be referenced by index variable "j", then by choosing appropriate values for i and j, we can access any storage location inside C and retrieve the value at that location.

Similarly, by varying the row and column index variables independently, we can STORE any values we wish INTO specific C array locations. So for example if I wrote the Matlab statement , I would store the value 1.0 INTO the C array, at the position row 1, column 3.

Previously we used one single FOR loop to store values into a one-dimensional array. Now we will need two FOR loops because we're dealing with two-dimensional arrays. The strategy to store values in the C array will be as follows: In one FOR loop we will vary the index variable "i", to begin at row 1 and move down C's rows one at a time until we get to C's last row. But, each time we increment the variable "i" by one step---thus addressing a new row of C---we will vary the index variable "j" OVER ALL OF C's COLUMNS. The net effect will be to step down the C array, row by row, and for each row, store values into each of its column positions across that row, from left to right, all the way across, before moving on to the next row.

Here's the Matlab code we would use to fill the 3x3 array C with the value 1.0 in each array position:

for i=[1:3]
  for j=[1:3]
    C(i,j) = 1.0
  end
end

What's going to happen? We'll enter the first FOR loop (or, "outer FOR loop"). When we do, index variable "i" is set to the value 1 (integer 1, not 1.0!). And then the second FOR loop (or, "inner FOR loop") is entered. Remember that index variable "i" still holds the value 1. In the inner FOR loop, index variable "j" is set to the value 1 and the assignment statement , is executed. C(1,1) appears on the left hand side of the assignment statement precisely because index variable "i" currently holds a value of 1, and index variable "j" currently holds a value of 1. The inner FOR loop now begins AGAIN and this time the index variable "j" is set to the value 2, and the assignment statement is executed. C(1,2) appears on the left hand side of this statement because while index variable "i" STILL holds a value of 1 (we're not finished with the outer FOR loop yet!), index variable "j" has had its value reset from 1 to 2 by the inner FOR loop. So in the assignment statement , "i" equals 1 and "j" equals 2. After the assignment statement executes a second time, the inner FOR loop begins AGAIN, resetting its index variable "j" to the value of 3. That means the assignment statement is executed. And now, the inner FOR loop is finished because index variable "j" is only given the values 1, 2 and 3 by the inner FOR loop. At this point, the outer FOR loop has just finished its work for the index variable "i" equal to 1. NOW, the outer FOR loop resets the value of "i" to 2, and, we begin again!

NOTE: When we begin the outer FOR loop again, it's important to realize that the value of index variable "j" will be RESET to 1 by the inner FOR loop, as that loop begins its next execution. It does not retain its old value of 3. Thus, the second time through the inner FOR loop will result in the value 1.0 being assigned to C array positions C(2,1), C(2,2) and C(2,3), corresponding to index variable "i" being set to the value 2 and index variable "j" varied from 1 to 3. You can now guess that the outer FOR loop will execute one final time, with its index variable "i" set to 3, and with inner FOR loop index variable j varied from 1 to 3. And that's exactly what happens. The net effect is that we visit ALL the storage locations in the C array. In this case, when we visit a location, we assign the value 1.0 to that location.

What we've just done is work through a detailed example of a NESTED FOR LOOP structure. This is the basic structure we'll use to access positions inside two dimensional arrays.

Now, not all two dimensional arrays are square, however, like the 3x3 array C. We can have arrays of various shapes. We're already familiar with 1xN arrays, which we've used extensively in our iterative programming exercises. Now it's time to familiarize ourselves with arrays of other dimensions.

For example, let's say we wanted to create a 4x6 array called "D", and fill each of its positions with the value 2.75. How would we write that Matlab code? Like this:

for i=[1:4]
  for j=[1:6]
    D(i,j) = 2.75
  end
end

That's it. That code does the trick. We have four rows. So we vary the outer FOR loop index "i" from 1 to 4. We have six columns. So we vary the inner FOR loop index "j" from 1 to 6. The result is a 4x6 array called "D" that has the value 2.75 assigned to each of its storage locatons. There are 24 total storage locations in D.

Nested FOR loop structures give us a powerful means of addressing individual storage locations inside arrays, and, of performing mathematical operations on the values stored at these locations. In the next short Matlab tutorial we'll use nested FOR loops to step through all the elements of an array and IF statements to make decisions based on the values that we find at each position. To accomplish this, we'll learn some basics about Matlab's IF statement.

7. Resources

A visual introduction to two-dimensional arrays (matrices) and nested for loops by Jmarr: ppt

Personal tools