Problem 3: Generate Permutations (200pts)

Given a sequence of unique elements, a permutation of the sequence is a list containing the elements of the sequence in arbitrary order. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are some of the permutations of the sequence [1, 2, 3]. [] is the only permutations of [].

Implement permutations, a generator function that takes in a sequence seq and returns a generator that yields all permutations of seq.

Permutations may be yielded in any order. Note that the doctests test whether you are yielding all possible permutations, but not the order. The built-in sorted function takes in an iterable object and returns a list containing the elements of the iterable in non-decreasing order.

Hint1: If you had the permutations of all the elements in seq not including the first element, how could you use that to generate the permutations of the full seq?

Hint2: There is no need to use some advanced non-recursive algorithms, which you may find on the Internet. Combination of yield and recursion is sufficient.

def permutations(seq):
    """Generates all permutations of the given sequence. Each permutation is a
    list of all elements in seq. The permutations could be yielded in any order.

    >>> perms = permutations([100])
    >>> type(perms)
    <class 'generator'>
    >>> next(perms)
    [100]
    >>> try: #this piece of code prints "No more permutations!" if calling next would cause an error
    ...     next(perms)
    ... except StopIteration:
    ...     print('No more permutations!')
    No more permutations!
    >>> sorted(permutations([1, 2, 3])) # Returns a sorted list containing elements of the generator
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    >>> 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']]
    """
    "*** YOUR CODE HERE ***"