Using nested loops

So what can we do with all these nested loops? Well, one of the things they're good for is figuring out all the possible permutations and combinations of a series of decisions.

WORD BOX

Permutation is a mathematical term that means a unique way of combining a set of things. Combination means something very similar. The difference is that, with a combination, the order doesn't matter, but with a permutation, the order does matter.

If I asked you to pick three numbers from 1 to 20, you could pick

and so on. If we tried to make a list of all the permutations of three numbers from 1 to 20, these two would be separate entries:

That's because, with permutations, the order in which they appear matters. If we made a list of all the combinations, all these would count as a single entry:

That's because order doesn't matter for combinations.

The best way to explain this is with an example. Let's imagine you're running a hot dog stand at your school's spring fair, and you want to make a poster showing how to order all possible combinations of hot dog, bun, ketchup, mustard, and onions by number. So we need to figure out what all the possible combinations are.

One way to think about this problem is to use something called a decision tree. The next figure shows a decision tree for the hot dog problem.

Start

Start

etc.

Each decision point has only two choices, Yes or No. Each different path down the tree describes a different combination of hot dog parts. The path I highlighted says "Yes" for hot dog, "No" for bun, "Yes" for mustard, and "Yes" for ketchup.

Now we're going to use nested loops to list all the combinations—all the paths through the decision tree. Because there are five decision points, there are five levels in our decision tree, so there will be five nested loops in our program. (Above figure only shows the first four levels of the decision tree.)

Type the code in listing 11.6 into an IDLE (or SPE) editor window, and save it as hotdogl.py.

Listing 11.6 Hot dog combinations print "\tDog \tBun \tKetchup\tMustard\tOnions" count = 1

print "#", count, "\t", print dog, "\t", bun, "\t", ketchup, "\t", print mustard, "\t", onion count = count + 1

dog / loop bun loop ketchup loop mustard loop onion loop

See how the loops are all one inside the other? That's what nested loops really are—loops inside other loops.

■ The bun loop runs twice for each iteration of the dog loop. So it runs 2 x 2 = 4 times.

■ The ketchup loop runs twice for each iteration of the dog loop. So it runs 2 x 2 x 2 = 8 times.

The innermost loop (that's the one farthest in—the onion loop) runs 2 x 2 x 2 x 2 x 2 = 32 times. This covers all the possible combinations. So there are 32 possible combinations.

If you run the program in listing 11.6, you should get something like this:

RESTART

>>>

■---RESTART

>>>

Dog

Bun

Ketchup Mustard Onions

# 1

0

0

0

0

0

# 2

0

0

0

0

1

# 3

0

0

0

1

0

# 4

0

0

0

1

1

# 5

0

0

1

0

0

# 6

0

0

1

0

1

# 7

0

0

1

1

0

# 8

0

0

1

1

1

# 9

0

1

0

0

0

# 10

0

1

0

0

1

# 11

0

1

0

1

0

# 12

0

1

0

1

1

# 13

0

1

1

0

0

# 14

0

1

1

0

1

# 15

0

1

1

1

0

# 16

0

1

1

1

1

# 17

1

0

0

0

0

# 18

1

0

0

0

1

# 19

1

0

0

1

0

# 20

1

0

0

1

1

# 21

1

0

1

0

0

# 22

1

0

1

0

1

# 23

1

0

1

1

0

# 24

1

0

1

1

1

# 25

1

1

0

0

0

# 26

1

1

0

0

1

# 27

1

1

0

1

0

# 28

1

1

0

1

1

# 29

1

1

1

0

0

# 30

1

1

1

0

1

# 31

1

1

1

1

0

# 32

1

1

1

1

1

The five nested loops run through all possible combinations of dog, bun, ketchup, mustard, and onion.

In listing 11.6, we used the tab character to line everything up. That's the \t parts. We haven't talked about print formatting yet, but if you want to know more about it, you can have a peek at chapter 21.

Mmmmm That's one good dog!

We used a variable called count to number each combination. So, for example, a hot dog with bun and mustard would be #27. Of course, some of the 32 combinations don't make sense. (A hot dog with no bun but with mustard and ketchup would be a little messy.) But you know what they say: "The customer is always right!"

0 0

Post a comment