## Donuts and Do Loops.## Penelope NomRecently my friend Cary asked me to stop at a donut shop that sells five varieties, and buy a dozen donuts. She didn't say how many of each type to buy so I began to wonder: in how many ways can you buy a dozen donuts from an unlimited supply of 5 types of donuts? This seems similar to another problem I looked at that had to do with using permutations to solve problems like: in how many ways can we rearrange the letters in the word ABRACADABRA to form a new 'word'? Here a new 'word' is one that looks different. We looked at this problem in a couple of ways one of which was to first choose where the 5 A's can go in the 11 letter 'word', now place the 2 B's in the remaining 6 spots, next place the 2 R's and finally place the C and the D. Thus the number of 'words' is
[11]C[5]*[6]C[2]*[4]C[2]*[2]C[1]*[1]C[1] = 11!/5!2!2!1!1! = 83,160.
The key to the donut problem is to think of how many distinct ways you can line up 12 x's and 4 /'s to make a `word'. Why? Because there is a one to one correspondence between such lineups and possible purchases -- the `word' xx/xxx//xxxxxx/x corresponds to 2 of type 1, 3 of type 2, 0 of type 3, 6 of type 4 and 1 of type 5 etc. Thus there are
[16]C[4]*[12]C[12] = [16]C[4] = 1820
ways to buy the donuts.
I now want to relate this `word' type problem to a real-life situation that crops up in designing computer programs. In trying to write efficient programs it is important for the programmer to know how many steps the computer is executing; in this manner the programmer can estimate how fast their program will run. A simple situation in what may be a complicated program is the situation whereby the computer is instructed to do a particular calculation a number of times in what is called a `Do Loop'. An simple example of this is as follows:
(set the counter to 0) c:=0 For i = 1 to j do For j = 1 to k do For k = 1 to 10 do (increment the counter by 1) c:= c+1How many times does the counter get increased? Equivalently, how many operations is the computer performing as it goes through this loop?
What we have to do is count all the possible choices for i, j and k where 1 <= i <= j <= k <= 10, i.e. all triples {i, j, k} where 1 <= i <= j <= k <= 10. These range through {1, 1, 1}, {1, 1, 2},{1, 2, 2}, ... {3, 6, 7}, ..., {10, 10, 10}. Let's look at this as a donut problem. I claim that the answer is the same as the answer to the problem of how many ways could I buy 3 donuts from 10 types! If we solved this as we did above we would make a `word' from 3 x's and 9 /'s. The number of ways to do this is [12]C[3] = 220 ways. How does this solve the do loop question? Look at a possible donut selection: //x///x/x/// -- this says buy a donut of type 3, type 6 and type 7. But this is also a triple {3, 6, 7} of the form {i, j, k} where 1 <= i <= j <= k <= 10 as we needed in the do loop question. Thus the counter will be incremented 220 times!
More generally, the do loop
(set the counter to 0) c:=0 For i = 1 to j do For j = 1 to k do For k = 1 to m do For m = 1 to n do For n = 1 to p do (increment the counter by 1) c:= c+1corresponds to finding 5-tuples {i, j, k, m, n} where 1 <= i <= j <= k <= m <= n <= p. This corresponds to buying 5 donuts from p types which we know can be done in [5+p -1]C[5] ways. So the next time someone asks you what you are doing in the donut shop tell them you are counting the number of steps in a multiple do loop. To return to the previous page use your browser's back button. |