PYTHON:
3. (12 points) As you might've guessed, the k_subsets naive function is not very efficient. In the pizza example, it has to consider all 65,536 topping combinations to find the 3-topping combinations, even though there are only 560 3-topping combinations. Much unnecessary work! Here's a more direct way of finding the k-subsets of S. Like the power set algorithm from Problem 1, this one is recursive. Let's start with a specific example. Suppose we want to find all 2-subsets of the set {x,y,z}. Remove an arbitrary element from {x,y,z}. Let's say we remove the element z, so the set is now just {y, z}. First, we'll consider the 2-subsets that do contain x. - Find all 1-subsets of {y, z}: {y}, {2} - Insert x into each of those 1-subsets: {x,y}, {2,2} Now, we'll consider the 2-subsets that don't contain x. This just requires finding all the 2-subsets of {y, z}; there's only one of these (the set {y, z} itself). Combine the 2-subsets from above to get the answer. In general, to find the k-subsets of set S: Remove an arbitrary element x ES. S is now smaller by one element. Consider the k-subsets that do contain x: find all (k 1)-subsets of S, and insert into each of those subsets. Consider the k-subsets that don't contain x: find all k-subsets of S. Combine the k-subsets from above to get the answer. Write a Python function k subsets_better(S, k) that uses the recursive algorithm presented above to return a set containing all the k-subsets of S. As before, represent the sets using Python lists. If k is not valid (i.e., negative, or greater than S), this function should return the empty list, []. 3. (12 points) As you might've guessed, the k_subsets naive function is not very efficient. In the pizza example, it has to consider all 65,536 topping combinations to find the 3-topping combinations, even though there are only 560 3-topping combinations. Much unnecessary work! Here's a more direct way of finding the k-subsets of S. Like the power set algorithm from Problem 1, this one is recursive. Let's start with a specific example. Suppose we want to find all 2-subsets of the set {x,y,z}. Remove an arbitrary element from {x,y,z}. Let's say we remove the element z, so the set is now just {y, z}. First, we'll consider the 2-subsets that do contain x. - Find all 1-subsets of {y, z}: {y}, {2} - Insert x into each of those 1-subsets: {x,y}, {2,2} Now, we'll consider the 2-subsets that don't contain x. This just requires finding all the 2-subsets of {y, z}; there's only one of these (the set {y, z} itself). Combine the 2-subsets from above to get the answer. In general, to find the k-subsets of set S: Remove an arbitrary element x ES. S is now smaller by one element. Consider the k-subsets that do contain x: find all (k 1)-subsets of S, and insert into each of those subsets. Consider the k-subsets that don't contain x: find all k-subsets of S. Combine the k-subsets from above to get the answer. Write a Python function k subsets_better(S, k) that uses the recursive algorithm presented above to return a set containing all the k-subsets of S. As before, represent the sets using Python lists. If k is not valid (i.e., negative, or greater than S), this function should return the empty list, []
