Lab 6 Solutions

lab06.zip

Solution Files

Required Questions

Tree Recursion!

Q1: Merge Numbers

Write a procedure merge(n1, n2), which takes numbers with digits in decreasing order and returns a single number with all of the digits of the two in decreasing order. Any number merged with 0 will be that number (treat 0 as having no digits). Use recursion.

def merge_numbers(n1, n2):
    """Merges two numbers that have decreasing digits.

    >>> merge_numbers(31, 42)
    4321
    >>> merge_numbers(21, 0)
    21
    >>> merge_numbers(21, 31)
    3211
    """
    if n1 == 0:
        return n2
    elif n2 == 0:
        return n1
    elif n1 % 10 < n2 % 10:
        return merge_numbers(n1 // 10, n2) * 10 + n1 % 10
    else:
        return merge_numbers(n1, n2 // 10) * 10 + n2 % 10

Use Ok to test your code:

python3 ok -q merge_numbers

Q2: Non-Decreasing Subsequences

We want to write a function that takes a list and returns a list of lists, where each individual list is a subsequence of the original input.

However, we have a condition: we only want the subsequences for which consecutive elements are nondecreasing. For example, [1, 3, 2] is a subsequence of [1, 3, 2, 4], but since 2 < 3, this subsequence would not be included in our result.

You may assume that the list passed in as s contains only nonnegative elements.

You may use the insert_into_all helper function.

def insert_into_all(item, lsts):
    """Assuming that lsts is a list of lists, return a new list consisting of
    all the lists in lsts, but with item added to the front of each.

    >>> lsts = [[], [1, 2], [3]]
    >>> insert_into_all(0, lsts)
    [[0], [0, 1, 2], [0, 3]]
    """
    return [[item] + lst for lst in lsts]

def non_decrease_subseqs(s):
    """Return a nested list of all subsequences of S (a list of lists) 
    for which the elements of the subsequence are nondecreasing. The 
    subsequences can appear in any order. You can assume S is a list.

    >>> seqs = non_decrease_subseqs([1, 3, 2])
    >>> sorted(seqs)
    [[], [1], [1, 2], [1, 3], [2], [3]]
    >>> non_decrease_subseqs([])
    [[]]
    >>> seqs2 = non_decrease_subseqs([1, 1, 2])
    >>> sorted(seqs2)
    [[], [1], [1], [1, 1], [1, 1, 2], [1, 2], [1, 2], [2]]
    """
    def subseq_helper(s, prev):
        if not s:
            return [[]]        elif s[0] < prev:
            return subseq_helper(s[1:], prev)        else:
            a = subseq_helper(s[1:], s[0])
            b = subseq_helper(s[1:], prev)
            return insert_into_all(s[0], a) + b
    return subseq_helper(s, 0)

Use Ok to test your code:

python3 ok -q non_decrease_subseqs

Q3: Partition

The number of partitions of a positive integer n is the number of ways in which n can be expressed as the sum of positive integers in increasing order. For example, the number 5 has 7 partitions.

5 = 5
5 = 1 + 4
5 = 2 + 3
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 1 + 1 + 1

Write a tree-recursive function partition(n) that returns the number of partitions of n.

Hint: Introduce a helper function that computes partitions of n using only a subset of the integers less than or equal to n. Once you have done so, you can use very similar logic to the count_change function from the lecture notes:

def partition(n):
    """Return the number of partitions of positive integer n.

    >>> partition(5)
    7
    >>> partition(10)
    42
    >>> partition(15)
    176
    >>> partition(20)
    627
    """
    return part_max(n, n)

def part_max(n, m):
    """Return the number of partitions of n using integers up to m.

    >>> part_max(5, 3)
    5
    """
    if n < 0 or m <= 0:
        return 0
    if n == 0:
        return 1
    return part_max(n-m, m) + part_max(n, m-1)

Use Ok to test your code:

python3 ok -q partition

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.