*Due by 11:59pm on Saturday, 07/26*

**Readings:** You might find the following references
useful:

**Submission:** See the online submission
instructions. We have provided a hw9.py starter file for the questions
below.

Implement the iterable interface for the `Link`

class. Do *not* assume that we already have the `__getitem__`

method defined.

```
class Link:
"""A recursive list, with Python integration."""
empty = None
def __init__(self, first, rest=empty):
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is Link.empty:
rest = ''
else:
rest = ', ' + repr(self.rest)
return 'Link({}{})'.format(self.first, rest)
def __str__(self):
if self.rest is Link.empty:
rest = ''
else:
rest = ' ' + str(self.rest)[2:-2]
return '< {}{} >'.format(self.first, rest)
"""
Implement the iterable interface for the Link class.
You will need to return an instance of an iterator
object in the __iter__ method.
"""
def __iter__(self):
"""
>>> l = list_to_link([1, 2, 3, 4])
>>> i = iter(l)
>>> hasattr(i, '__next__')
True
>>> l2 = list_to_link([3, 1, 4, 1])
>>> for el in l2:
... print(el)
...
3
1
4
1
"""
"*** YOUR CODE HERE ***"
class LinkedListIterator:
"*** YOUR CODE HERE ***"
def list_to_link(lst):
"""
This is a convenience method which
converts a Python list into a linked list.
DO NOT USE THIS IN ANY OF YOUR SOLUTIONS.
"""
ll = Link.empty
for elem in lst[::-1]:
ll = Link(elem, ll)
return ll
```

Recall that an *iterable* object must have an `__iter__`

method which returns an *iterator* object. You will need to define a `LinkedListIterator`

class to complete the implementation.

You should be able to do a `for`

loop over the elements of a linked list once you have correctly implemented the interface.

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 function which takes in a `lst`

and outputs a list of all permutations of `lst`

(see doctest for examples).

```
def list_perms(lst):
"""
Returns a list of all permutations of lst.
>>> p = list_perms([1, 2, 3])
>>> p.sort()
>>> p
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> p1 = list_perms([0, 1])
>>> p1.sort()
>>> p1
[[0, 1], [1, 0]]
"""
if lst == []:
return None # REPLACE ME
prev_perms = list_perms(lst[1:])
result = []
for perm in prev_perms:
for i in range(len(lst)):
"*** YOUR CODE HERE ***"
return result
```

Feel free to replace the `for`

loops with list comprehensions if you would rather use that.

One application of list permutations is in solving math puzzles like this one:

`___ * ___ - ___ - ___ // ___ + ___ - ___ // ___ * ___ = 7`

The goal is to arrange the numbers from `1`

to `9`

in each of the blank spots such that the expression evaluates to `7`

. We have included a class `MathPuzzle`

, which randomly generates a puzzle out of a given `rng`

. In the example above, `rng`

is `9`

. You can call `print`

on the `MathPuzzle`

object to get a representation like the one shown above.

The `MathPuzzle`

class has a `check_solution`

method, which takes in a list of numbers between `1`

and the `range`

of the puzzle and checks to see if they satisfy the expression. In this case, one solution would be

`[1, 3, 2, 9, 5, 7, 4, 8, 6]`

Using your code for `list_perms`

, write `solve_list_perms`

, which takes in a `MathPuzzle`

object and returns a solution to the puzzle. Note that a given `MathPuzzle`

may have multiple possible solutions; your program only needs to return the first solution you encounter.

```
def solve_list_perms(puzzle):
"""
Solves a MathPuzzle using a list of permutations;
returns the first correct answer it encounters.
"""
"*** YOUR CODE HERE ***"
```

We've provided a `TestPuzzle`

class which creates a puzzle out of a pre-determined expression so you can test your code:

```
class TestPuzzle(MathPuzzle):
"""
Creates a MathPuzzle out of the given expression.
>>> test = TestPuzzle([1, '+', 2, '*', 3])
>>> print(test)
___ + ___ * ___ = 7
>>> test.check_solution([1, 2, 3])
True
>>> test.check_solution([1, 3, 2])
True
>>> test.check_solution([2, 3, 1])
False
"""
def __init__(self, expression):
self.expression = [str(el) for el in expression]
self.puzzle = [el for el in expression if el in MathPuzzle.ops]
self.value = eval(''.join(self.expression))
self.range = len(self.puzzle) + 1
```

Be sure to make up puzzles yourself and load the file interactively. Your program may find a different solution from the one you inputted - this is fine as long as it still evaluates to the correct `value`

.

You might have noticed that with larger puzzles, your code for `solve_list_perms`

was quite slow. This is because `list_perms`

computes and outputs *all* permutations at once, and we have to wait for that entire process to finish before we can start testing. This implementation was also space inefficient, because it had to store all permutations when only a handful would have been a valid solution to the puzzle.

To fix these issues, write `generate_perms`

, a more efficient way to get permutations. `generate_perms`

is a generator function which yields each permutation of `lst`

one by one, so it never has to store the entire set of permutations in memory at one time.

```
def generate_perms(lst):
"""
Generates the permutations of lst one by one.
>>> perms = generate_perms([1, 2, 3])
>>> hasattr(perms, '__next__')
True
>>> p = list(perms)
>>> p.sort()
>>> p
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
"""
"*** YOUR CODE HERE ***"
```

See Lecture 16 for an example of converting a list-based solution to a generator solution (`subsets`

).

To see the difference, write `solve_gen_perms`

, which solves a `MathPuzzle`

using `generate_perms`

instead of `list_perms`

.

```
def solve_gen_perms(puzzle):
"""
Solves a MathPuzzle by generating permutations;
returns the first correct answer it encounters.
"""
"*** YOUR CODE HERE ***"
```

Try making a larger `MathPuzzle`

(with a `rng`

of `15`

or so) and solve it using both methods. `solve_gen_perms`

should be significantly faster.

Like functions, generators can also be *higher-order*. For this problem, we will be writing `remainders_generator`

, which yields a series of generator objects.

```
def remainders_generator(m):
"""
Takes in an integer m, and yields m different remainder groups
of m.
>>> remainders_mod_four = remainders_generator(4)
>>> for rem_group in remainders_mod_four:
... for i in range(3):
... next(rem_group)
...
0
4
8
1
5
9
2
6
10
3
7
11
"""
"*** YOUR CODE HERE ***"
```

`remainders_generator`

takes in an integer `m`

, and yields `m`

different generators: a generator of multiples of `m`

, a generator of
natural numbers which leave a remainder of 1 when divided by `m`

, and
so on up to a remainder of `m - 1`

.

Note that if you have implemented this correctly, each of the generators yielded by `remainder_generator`

will be *infinite* - you can keep calling `next`

on them forever without running into a `StopIteration`

exception.

**Hint**: Consider defining an inner generator function. What arguments should it take in? Where should you call it?