Ice Cream Bowls

Pages or lab needs renaming so they aren't duplicative. --MF, 6/15/20

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.

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,

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.
  1. How many two-scoop bowls are there? Find a systematic way of listing them.
  2. Look for a way to describe the problem using recursion.
  3. 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.
  1. 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.
  2. 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!
  1. Write a procedure that, given a list of available flavors, reports a list of all possible bowls regardless of the number of scoops.
  2. 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.)