Page 2: Listing the Subsets

Unit 8, Lab 3, Page 2

On this page, you will learn how to generalize the ice cream solution to list the subsets of any set.

Given a set of things, a subset contains zero or more of its elements, without duplicates. As was true for ice cream bowls, order doesn’t matter.

{Banana, Apple} is the same subset as {Apple, Banana}.

For example, given the set {Apple, Orange, Banana} there are one-element subsets like {Banana} and two-element subsets like {Apple, Banana}. The original set {Apple, Orange, Banana} counts, and so does the empty set{} with zero elements.

  1. Write down all the subsets of {Apple, Orange, Banana}. How many are there?

  1. Write down all the subsets of {Pretzel, Apple, Orange, Banana}. Try to do this with as little work as possible. Talk with Your Partner Describe how you did it.

  1. Now create a subsets block that takes a list as input and reports a list of lists in which each item is a subset of the original input list. The order in which the subsets appear in the output list doesn’t matter, but each subset must appear exactly once. The result might look like this:
    subsets(list{Apple, Orange, Banana}) reporting {{},{Banana}, {Orange}, {Banana, Orange},{Apple}, {Apple, Banana}, {Apple, Orange}, {Apple, Orange, Banana}}

    If you’re stuck after trying as many ideas as you can think of, . click here for some help

    • How many subsets does the empty set {} have?

    • What should subsets report in the base case? This is a hard part to get right!

    • How many subsets of {Pretzel, Apple, Orange, Banana} contain Pretzel? How many don’t?

    • Describe “the subsets of {Pretzel, Apple, Orange, Banana} that don’t contain Pretzel” without using the words “don’t contain.”

    • Here’s one version of what the code might look like, with many spaces to fill…
      subsets(set){if(){report()}else{...; report(append()())}}

Subsets and Efficiency

Here is one solution for the subsets block.

subsets(set){if(empty?(set)){report(list{})}else{report(append(subsets(all but first of(set)))(map(item(1) of (set) in front of ()) over(subsets(all but first of(set)))))}}

This solution for subsets makes the same recursive call twice, an inefficiency that can be corrected.

  1. Use a count variable to count how many recursive calls are made to find the 64 subsets of a six-element list.

  1. Figure out how to reduce the number of recursive calls by avoiding redundant calls.