Unit 8 Lab 3: Subsets, Page 1

Counting Ice Cream Bowls

In this lab, you will explore a classic computer science problem: subsets.

On this page, you will explore a familiar introduction to subsets: choosing flavors of ice cream.

A subset is a selection of items from a set; it can be none, all, or any number in between.

Where is this picture from and does it need attribution? --MF, 4/22/22

an image of a Simplex lock: five buttons numbered 1–5 over a doorknob with a keyhole

There are lots of problems that are about subsets. For example,

There are 20 students in the class and you want a committee of four. How many combinations of four people are there?
How many combinations are there for a Simplex lock? (A Simplex lock has five buttons. You can use each button at most once, but you can press more than one at the same time. See image at right.)
A store has eight flavors of ice cream. How many combinations of ice cream flavors can you chose for a bowl with a given number of scoops?

For now, all scoops must be different from one another. The order of the scoops doesn't matter: a bowl with vanilla and chocolate is the same as a bowl with chocolate and vanilla.

How many two-scoop bowls are there? Find a systematic way of listing them.
Look for a way to describe the problem using recursion.
"U8L3-Subsets"
You may want to use the append block.
Build a block that, given a variable-length input list of available flavors, reports a list with all two-scoop bowls. (Since a two-scoop bowl is represented as a list of two flavors, a list of bowls is a list of lists.)

The block you built for two-scoop bowls can help you build a block for three-scoop bowls.

Build a block that lists all three-scoop bowls, given a list of the available flavors. Remember, the order of the scoops doesn't matter, so think about how you might avoid listing the same bowl more than once.
That bowl either has chocolate, or doesn't.
Generalize to build a block that lists all n-scoop bowls, with an additional input giving the number of scoops. This will definitely need recursion!

Write a procedure that, given a list of available flavors, reports a list of all possible bowls regardless of the number of scoops.
Remove the restriction that each scoop must be a different flavor: Chocolate, chocolate, and chocolate is now allowed, and many more. (Note that this problem is technically no longer about subsets, because by definition a set can't have the same item twice.)