# Homework 11

*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:

# 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.