Due by 11:59pm on Thursday, 11/10

Instructions

Download hw11.zip.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more instructions on submitting assignments.

Using OK: If you have any questions about using OK, please refer to this guide.

Readings: You might find the following references useful:

• Section 2.9.3
• Section 4.2

Homework Questions

Question 1: In Order

Write a function that yields the entries of a valid binary search tree in sorted order.

def in_order(t):
    """
    Yields the entries of a valid binary search tree in sorted order.

    >>> b = BTree(5, BTree(3, BTree(2), BTree(4)), BTree(6))
    >>> list(in_order(b))
    [2, 3, 4, 5, 6]
    >>> list(in_order(bst([1, 3, 5, 7, 9, 11, 13])))
    [1, 3, 5, 7, 9, 11, 13]
    >>> list(in_order(BTree(1)))
    [1]
    """
    "*** YOUR CODE HERE ***"

Hint: The yield from expression is helpful if you want to yield all the values from another sequence.

Use OK to test your code:

python3 ok -q in_order

Question 2: Generate Permutations

Given a list of unique elements, a permutation of the list is a reordering of the elements. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are all permutations of the list [1, 2, 3].

Implement permutations, a generator function that takes in a lst and outputs all permutations of lst, each as a list (see doctest for an example).

def permutations(lst):
    """Generates all permutations of sequence LST. Each permutation is a
    list of the elements in LST in a different order.

    The order of the permutations does not matter.

    >>> sorted(permutations([1, 2, 3]))
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    >>> type(permutations([1, 2, 3]))
    <class 'generator'>
    >>> sorted(permutations((10, 20, 30)))
    [[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
    >>> sorted(permutations("ab"))
    [['a', 'b'], ['b', 'a']]
    """
    if not lst:
        yield []
        return
    "*** YOUR CODE HERE ***"

The order in which you generate permutations is irrelevant.

Hint: If you had the permutations of lst minus one element, how could you use that to generate the permutations of the full lst?

Use OK to test your code:

python3 ok -q permutations

permutations will be used as part of the AutoStyle study in the next question. Participation in AutoStyle is completely optional; you will receive full credit for this homework by completing questions 1 and 2.

Question 3: Run AutoStyle

This question is optional.

Once you have passed all the tests, invoke AutoStyle by running the command:

python3 ok --style -q permutations

AutoStyle will provide hints to help improve code style and composition. The process will take about 1 hour and must be completed in a single sitting.

When running AutoStyle, please don't place any print statements into your code. If you would like to test your code with print statements, try running it in a terminal on your computer.

If you run into any problems, please make a private post on Piazza tagged under the folder autostyle and include a screenshot of the error as well as a copy of your code.