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

## Instructions

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:

# 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]
"""
``````

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
``````

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.