Nested Loops Over Two Lists: is_subset, intersect, and Nine Sevens

When one list is scanned inside a loop over another, why do the lengths multiply, and why must a list built from the inputs count too?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Count is_subset's comparisons

The function below is is_subset from the video, changed to return a pair: the True/False answer and a counter comparisons. Right now the counter never moves. Add one line so it counts every e1 == e2 test, including the one that finds a match just before break. Keep the name is_subset_count(L1, L2).

def is_subset_count(L1, L2):
    comparisons = 0
    for e1 in L1:
        matched = False
        for e2 in L2:
            if e1 == e2:
                matched = True
                break
        if not matched:
            return False, comparisons
    return True, comparisons

# Add ONE line inside the function so that comparisons
# counts every e1 == e2 test the function performs.

def is_subset_count(L1, L2):
    comparisons = 0
    for e1 in L1:
        matched = False
        for e2 in L2:
            if e1 == e2:
                matched = True
                break
        if not matched:
            return False, comparisons
    return True, comparisons

# Add ONE line inside the function so that comparisons
# counts every e1 == e2 test the function performs.

Python runs in your browser

⌘/Ctrl + Enter runs

returns a (bool, int) pair

first example from the video: True after the right number of comparisons

second example: stops early on the missing 3

counts the matching comparison too

←Previous Which Loop Depends on n? compound and fib_iter Linear, g Quadratic Next Two Nested Loops, Three Thetas: diameter, all_digits, and a Hidden in →