Power set

From CS 61A Wiki
Jump to: navigation, search
Purge this page if the LaTeX typesetting doesn't render.

A power set of a set $A$ is the set of all subsets of $A$, including the empty set and the set $A$ itself. Mathematically, this can be represented $\mathcal P (S)=\{a\: |\: a\subseteq A\}$. For a more concrete example, let's examine the list:

lst = [1, False, "Hello"]

All subsets of lst must contain some number of the elements in lst and no elements that aren't in lst. This can range anywhere between zero elements (empty set), and all the elements (the set itself). Since, lst is a small list, we can list out all it's subsets below:

This is the empty set that contains no elements in lst

  • []

The following are the subsets that only contain one element

  • [1]
  • [False]
  • ["Hello"]

The following are the subsets that contain two elements (order doesn't matter)

  • [1, False]
  • [1, "Hello"]
  • [False, "Hello"]

This is the original set itself (so lst is a subset of lst)

  • [1, False, "Hello"]

The power set of lst, is a set that contains all of these subsets:

>>> powerset(lst)
[[], [1], [False], ["Hello"], [1, False], [1, "Hello"], [False, "Hello"], [1, False, "Hello]]


Problem

The problem can be stated as such:

Complete the definition of powerset which takes in a list as an argument and returns a new list containing all of the subsets of the argument list:
def powerset(lst):
    """Return a list containing all the subsets of lst.
 
    >>> powerset([])
    [[]]
    >>> powerset(["CS", [61, "A"]])
    [[], ["CS"], [[61, "A"]], ["CS", [61, "A"]]]
    >>> powerset([1, 2, 3])
    [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
    >>> powerset([2, 3])
    [[], [2], [3], [2, 3]]
    """
    "*** YOUR CODE HERE ***"

Approach

Overview

When we approach a problem recursively, we need to try and break it down into a smaller version of the same problem. Just like how a recursive factorial function utilizes the fact that $n!=n\cdot(n-1)!$ to make recursive calls, our approach to this recursive problem should do something similar. We need a recursive definition, which tells Python how to recurse through this problem, and a base case, which tells Python where to stop recursing.

Recursive Case

While it is sometimes easier to implement the base case first, the base case is not completely obvious in this example. For this problem, we will instead examine what should happen for the recursive case first. To do this let's look at the last two examples in the doctests shown below:


>>> powerset([1, 2, 3])
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
>>> powerset([2, 3])
[[], [2], [3], [2, 3]]


Here, we see that the list passed in the first case and the list passed in the second case only differ by the element 1, and that the second list is actually the "rest" of the first list. This sounds suspiciously like how we wrote recursive functions for linked lists... Let's try to see if a recursive call to power([1, 2, 3][1:]) would help us in some way. In other words, does powerset([1, 2, 3][1:]) help us build an answer to powerset([1, 2, 3])?


Since we want to see if we can build the result of powerset([1, 2, 3]) with the result of powerset([1, 2, 3][1:]) let's see what the outputs differ by, as well as whether or not they share common elements. Let's imagine we could somehow, perhaps manually, obtain the list of everything in powerset([1, 2, 3]) that isn't in powerset([1, 2, 3][1:]), the list of everything in both powerset([1, 2, 3]) and powerset([1, 2, 3][1:]), and just the output of powerset([1, 2, 3][1:])


# List of elements in powerset([1, 2, 3]) but not in powerset([1, 2, 3][1:])
[[1], [1, 2], [1, 3], [1, 2, 3]]
# List of elements in powerset([1, 2, 3]) and in powerset([1, 2, 3][1:])
[[], [2], [3], [2, 3]]
# Result of powerset([1, 2, 3][1:])
[[], [2], [3], [2, 3]]


Interesting. The results look extremely similar. In fact, the only elements that were in powerset([1, 2, 3]) but not in powerset([1, 2, 3][1:]) are the elements of powerset([1, 2, 3][1:]) with 1 added to them. So where did this 1 come from? It's the first element in [1, 2, 3] or [1, 2, 3][0]! As well, we note that all the elements in powerset([1, 2, 3][1:]) are in powerset([1, 2, 3][1:]). Now we can begin to outline what a recursive definition of powerset might look like.


def powerset(lst):
    """Pseudo-code for generating the power set of lst."""
    if base_case:
        return "We haven't figured this out yet"
    else:
        recursive_result = powerset("Rest of lst")
        new_elements = "Add first of lst to every elem in recursive_result"
        return "Combine the elements in recursive_result and new_elements"


Base Case

Now that we have a recursive definition to work with, the base case should come pretty easily. Since, the base case of a function tells us when to stop the recursion, let's look at the recursive call in powerset. It calls itself with the rest of the current lst as it's argument. This means at some point, we will end up with a list of no elements - an empty list. How many subsets are there of an empty list if a subset is defined as a set containing some number of elements in the original set and an empty list has no elements? Exactly one - the empty list! So what should we return? Let's think about the range of our function. powerset returns a list of subsets, so we should return the list that contains just the empty list!


def powerset(lst):
    """Pseudo-code for generating the power set of lst."""
    if empty_list:
        return "List containing the empty list"
    else:
        recursive_result = powerset("Rest of lst")
        new_elements = "Add first of lst to every elem in recursive_result"
        return "Combine the elements in recursive_result and new_elements"

Add to all

Now, we breezed over a pretty significant task when we built our recursive definition of powerset. We assumed there was some magical way of "Adding first of lst to every elem in recursive_result". This task was abstracted away to let us get the recursive idea behind powerset without worrying about the details. Here, we'll outline the concept behind a recursive procedure to do this.


def add_to_all(lst, elem):
    """Returns a list of lists where every element
    is a list in lst with elem added to it
 
    >>> add_to_all([[], [1]], 2)
    [[2], [1, 2]]
    """


Base Case

This one is pretty simple. What happens if we give add_to_all a list with no lists inside? Well, since there are no lists to add elem to, we can just return the empty list!

Recursive Case

If our input lst is not empty then we must have a first element, lst[0] that is a list. Adding elem to this list is simple as it is just lst[0] + list(elem). Now we want to combine this result with a list that has elem added to all the elements in the rest of our list... That problem sounds like the same one that we are solving right now. This is where we trust our recursive call to do the work for us.


def add_to_all(lst, elem):
    """Returns a list of lists where every element
    is a list in lst with elem added to it. This is
    psuedo-code.
 
    >>> add_to_all([[], [1]], 2)
    [[2], [1, 2]]
    """
    if empty_list:
        return empty_list
    recursive_result = add_to_all(rest_of_lst, elem)
    return "Combine lst[0] + list(elem) and recursive_result"