Difference between revisions of "Power set"

From CS 61A Wiki
Jump to: navigation, search
[unchecked revision][checked revision]
(Created page with "{{Purge}} 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...")
 
m ({{Sufficient-class}})
 
(10 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
{{Sufficient-class}}
 
{{Purge}}
 
{{Purge}}
 +
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:
 +
<source lang="python">lst = [1, False, "Hello"]</source>
  
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\.\text{if}\.a\subseteq A\}$. T is a puzzle that involves three pegs and <code>n</code> disks. The each disk is of a unique size, with smaller disks always going on top of larger disks on a peg. At the beginning of the puzzle, all the disks are stacked on one starting peg from smallest (on the top) to the largest (on the bottom). The goal is to make the necessary valid moves to move the disks from the <code>start</code> peg to the desired <code>end</code> peg.
+
All subsets of <code>lst</code> must contain some number of the elements in <code>lst</code> and no elements that aren't in <code>lst</code>. This can range anywhere between zero elements (empty set), and all the elements (the set itself). Since, <code>lst</code> is a small list, we can list out all it's subsets below:
  
Valid moves are such that
+
This is the empty set that contains no elements in <code>lst</code>
* Only one disk may be moved at a time.
+
* <code>[]</code>
* Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
+
The following are the subsets that only contain one element
* No disk may be placed on top of a smaller disk.
+
* <code>[1]</code>
 +
* <code>[False]</code>
 +
* <code>["Hello"]</code>
 +
The following are the subsets that contain two elements (order doesn't matter)
 +
* <code>[1, False]</code>
 +
* <code>[1, "Hello"]</code>
 +
* <code>[False, "Hello"]</code>
 +
This is the original set itself (so <code>lst</code> is a subset of <code>lst</code>)
 +
* <code>[1, False, "Hello"]</code>
 +
 
 +
The power set of <code>lst</code>, is a set that contains all of these subsets:
 +
 
 +
<source lang="python">
 +
>>> powerset(lst)
 +
[[], [1], [False], ["Hello"], [1, False], [1, "Hello"], [False, "Hello"], [1, False, "Hello]]
 +
</source>
  
  
 
== Problem ==
 
== Problem ==
 
The problem can be stated as such:
 
The problem can be stated as such:
<blockquote>Complete the definition of <code>towers_of_hanoi</code> which prints out the steps to solve this puzzle for any number of <code>n</code> disks starting from the <code>start</code> rod and moving them to the <code>end</code> rod:
+
<blockquote>Complete the definition of <code>powerset</code> which takes in a list as an argument and returns a new list containing all of the subsets of the argument list:
 
<source lang="python">
 
<source lang="python">
def towers_of_hanoi(n, start, end):
+
def powerset(lst):
     """Print the moves required to solve the towers of hanoi game if we start
+
     """Return a list containing all the subsets of lst.
    with n disks on the start pole and want to move them all to the end pole.
+
  
     The game is to assumed to have 3 poles (which is traditional).
+
     >>> powerset([])
 
+
    [[]]
     >>> towers_of_hanoi(1, 1, 3)
+
     >>> powerset(["CS", [61, "A"]])
     Move 1 disk from rod 1 to rod 3
+
     [[], ["CS"], [[61, "A"]], ["CS", [61, "A"]]]
     >>> towers_of_hanoi(2, 1, 3)
+
     >>> powerset([1, 2, 3])
     Move 1 disk from rod 1 to rod 2
+
     [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
    Move 1 disk from rod 1 to rod 3
+
     >>> powerset([2, 3])
    Move 1 disk from rod 2 to rod 3
+
     [[], [2], [3], [2, 3]]
     >>> towers_of_hanoi(3, 1, 3)
+
     Move 1 disk from rod 1 to rod 3
+
    Move 1 disk from rod 1 to rod 2
+
    Move 1 disk from rod 3 to rod 2
+
    Move 1 disk from rod 1 to rod 3
+
    Move 1 disk from rod 2 to rod 1
+
    Move 1 disk from rod 2 to rod 3
+
    Move 1 disk from rod 1 to rod 3
+
 
     """
 
     """
 
     "*** YOUR CODE HERE ***"
 
     "*** YOUR CODE HERE ***"
 
 
def move_disk(start, end):
 
    print("Move 1 disk from rod", start, "to rod", end)
 
 
</source></blockquote>
 
</source></blockquote>
  
 
== Approach ==
 
== Approach ==
 +
 
=== Overview ===
 
=== 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 a recursive <code>factorial</code> function utilizes the fact that $n!=n\cdot(n-1)!$ to make recursive calls, our approaches to other recursive problems 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.
+
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 <code>factorial</code> 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:
 +
 
 +
 
 +
<source lang="python">
 +
>>> powerset([1, 2, 3])
 +
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
 +
>>> powerset([2, 3])
 +
[[], [2], [3], [2, 3]]
 +
</source>
 +
 
 +
 
 +
Here, we see that the list passed in the first case and the list passed in the second case only differ by the element <code>1</code>, 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 <code>power([1, 2, 3][1:])</code> would help us in some way. In other words, does <code>powerset([1, 2, 3][1:])</code> help us build an answer to <code>powerset([1, 2, 3])</code>?
 +
 
 +
 
 +
Since we want to see if we can build the result of <code>powerset([1, 2, 3])</code> with the result of <code>powerset([1, 2, 3][1:])</code> 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 <code>powerset([1, 2, 3])</code> that isn't in <code>powerset([1, 2, 3][1:])</code>, the list of everything in both <code>powerset([1, 2, 3])</code> and <code>powerset([1, 2, 3][1:])</code>, and just the output of <code>powerset([1, 2, 3][1:])</code>
 +
 
 +
 
 +
<source lang="python">
 +
# 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]]
 +
</source>
 +
 
 +
 
 +
Interesting. The results look extremely similar. In fact, the only elements that were in <code>powerset([1, 2, 3])</code> but not in <code>powerset([1, 2, 3][1:])</code> are the elements of <code>powerset([1, 2, 3][1:])</code> with <code>1</code> added to them. So where did this <code>1</code> come from? It's the first element in <code>[1, 2, 3]</code> or <code>[1, 2, 3][0]</code>! As well, we note that all the elements in <code>powerset([1, 2, 3][1:])</code> are in <code>powerset([1, 2, 3][1:])</code>. Now we can begin to outline what a recursive definition of <code>powerset</code> might look like.
 +
 
 +
 
 +
<source lang="python">
 +
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"
 +
</source>
 +
 
  
 
=== Base Case ===
 
=== Base Case ===
So let's start with the base case. The base case should be a case where we do not need to make recursive calls to know what the answer is ($1!=1$, for <code>factorial</code>). In <code>towers_of_hanoi</code>, what is the easiest base case to solve? What should the function do in that 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 <code>powerset</code>. It calls itself with the rest of the current <code>lst</code> 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. <code>powerset</code> returns a list of subsets, so we should return the list that contains just the empty list!
  
=== Recursive Case ===
 
Now what about the recursive case? Trying to figure out the algorithm to correctly move each disk is a bit difficult, so let's only deal with the nth disk, or the bottom-most one, and somehow have recursion deal with the other <code>n - 1</code> disks. Here, we have the start of the problem:
 
  
[[File:hanoi0.png]]
+
<source lang="python">
 +
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"
 +
</source>
  
To move all the disks from start to end we need to eventually move disk n. But since we can only move the top-most disk of any tower, we have to first move all the <code>n - 1</code> disks to the offset, so that later we can
+
== Add to all ==
move disk <code>n</code> to the <code>end</code>:
+
Now, we breezed over a pretty significant task when we built our recursive definition of <code>powerset</code>. We assumed there was some magical way of <code>"Adding first of lst to every elem in recursive_result"</code>. This task was abstracted away to let us get the recursive idea behind <code>powerset</code> without worrying about the details. Here, we'll outline the concept behind a recursive procedure to do this.
  
[[File:hanoi1.png]]
 
  
At this point, disk <code>n</code> is free to move, so we can place it at the end:
+
<source lang="python">
 +
def add_to_all(lst, elem):
 +
    """Returns a list of lists where every element
 +
    is a list in lst with elem added to it
  
[[File:hanoi2.png]]
+
    >>> add_to_all([[], [1]], 2)
 +
    [[2], [1, 2]]
 +
    """
 +
</source>
  
And then, we just need to move the <code>n - 1</code> disks to the end as well:
 
  
[[File:hanoi3.png]]
+
=== Base Case ===
 +
This one is pretty simple. What happens if we give <code>add_to_all</code> a list with no lists inside? Well, since there are no lists to add <code>elem</code> to, we can just return the empty list!
  
At this point, the only thing that we may be unsure of is how to move the <code>n - 1</code> disks from the start to the offset. But note exactly what <code>towers_of_hanoi</code> does. The function <code>towers_of_hanoi</code> prints the procedure of how to move <code>n</code> disks from <code>start</code> to the <code>end</code>.
+
=== Recursive Case ===
 +
If our input <code>lst</code> is not empty then we must have a first element, <code>lst[0]</code> that is a list. Adding <code>elem</code> to this list is simple as it is just <code>lst[0] + list(elem)</code>. Now we want to combine this result with a list that has <code>elem</code> 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.
  
And already, we've come across a smaller version of this problem! We need to move the n - 1 disks from start to the offset, which in itself is a towers_of_hanoi problem, only with a different destination, and one less disk. We encounter the problem again when after we move the nth disk, we need to move the n - 1 disks again to the end as well.
 
  
=== The Trick ===
+
<source lang="python">
Of course, we're not done defining towers_of_hanoi yet, but we know what the goal of it is anyways. Once we're finished, it should work as we had intended it to, so let's take a recursive leap of faith, and go ahead and make recursive calls to <code>towers_of_hanoi</code>to move the <code>n - 1</code> disks out of our way. The only thing that may be tricky is to figure out which peg is the "offset" peg. Consider the following:
+
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
! start !! end !! offset
+
    psuedo-code.
|-
+
|  1  ||  3  ||  2
+
|-
+
|  3  ||  1  ||  2
+
|-
+
|  1  ||  2  ||  3
+
|-
+
|  2  ||  1  ||  3
+
|-
+
|  2  ||  3  ||  1
+
|-
+
|  3  ||  2  ||  1
+
|-
+
|}
+
  
After a lot of thought, one might come up with <code>offset = 6 - start - end</code>. This is just an expression that matches the table above, so don't worry if you didn't come up with this.
+
    >>> 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"
 +
</source>

Latest revision as of 09:09, 9 July 2014

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"