Listing the Subsets

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?
  2. Write down all the subsets of {Pretzel, Apple, Orange, Banana}. Try to do this with as little work as possible.
    Add a question that gets at how 2 is just an augmentation of 1. --MF, 6/17/20 Talk with Your PartnerDescribe how you did it.
  3. MARY Note to self: this is hard. for example, in base case (subsets of empty list), you have to report a list containing the empty list. Add a question that gets at the base case.
    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()())}}
The following is all from a second page and needs to be properly integrated by Mary. --MF, 6/17/20

Subsets and Efficiency

MF: Scrap. Fold into the Subsets OP at the end.

If we keep this image anywhere (the image behind the hint), it needs to be rebuilt. --MF, 4/22/22

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. Using a count variable to count how many recursive calls are made to find the 64 subsets of a six-element list.
  2. Figure out how to reduce the number of recursive calls by avoiding redundant calls.