Difference between revisions of "Power set"
[unchecked revision]  [checked revision] 
Li.yang.yi (Talk  contribs) (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 ({{Sufficientclass}}) 

(10 intermediate revisions by 2 users not shown)  
Line 1:  Line 1:  
+  {{Sufficientclass}}  
{{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>  
−  +  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:  
−  +  This is the empty set that contains no elements in <code>lst</code>  
−  *  +  * <code>[]</code> 
−  *  +  The following are the subsets that only contain one element 
−  *  +  * <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>  +  <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  +  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 ***"  "*** YOUR CODE HERE ***"  
−  
−  
−  
−  
</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(n1)!$ to make recursive calls, our  +  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(n1)!$ 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):  
+  """Pseudocode 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 ===  
−  +  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!  
−  
−  
−  +  <source lang="python">  
+  def powerset(lst):  
+  """Pseudocode 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>  
−  +  == Add to all ==  
−  +  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.  
−  
−  +  <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  
−  [[  +  >>> add_to_all([[], [1]], 2) 
+  [[2], [1, 2]]  
+  """  
+  </source>  
−  
−  +  === 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!  
−  +  === 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.  
−  
−  =  +  <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. This is  
−  +  psuedocode.  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  >>> 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]]
Contents
Problem
The problem can be stated as such:
Complete the definition ofpowerset
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(n1)!$ 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): """Pseudocode 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): """Pseudocode 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 psuedocode. >>> 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"