Lab 5：可变性、迭代器与生成器ok 8 项通过

0. 这份作业在练什么

到 Lab 4 为止，你写的每个函数几乎都是「纯」的：给它一些值，它算出一个新值还给你，原来的东西一动不动。[1, 2] + [3] 造出一个新列表，n // 10 造出一个新整数。在这种世界里，「这个名字现在是什么值」就是全部真相，环境图里每个格子写一个数就够了。

Lab 5 把这个世界打破成两半：

• 可变性（mutability）：列表和字典这类对象可以被就地修改。于是「名字绑到什么值」不再是全部真相，你还得知道有几个名字指着同一个对象。s.append(6) 会让另一个跟 s 无关的变量 t 的打印结果跟着变——只要 t 和 s 指向同一个列表。这个现象叫别名（aliasing），是本次作业前半段全部的难点来源。
• 惰性求值（lazy evaluation）：迭代器（iterator）和生成器（generator）不把结果一次算完，而是每次调用 next 才往前挪一格，并且记住自己挪到了哪里。于是「这个表达式的值是什么」也不再是全部真相，你还得知道这个迭代器现在处在什么状态。

这两件事有一个共同的根：状态（state）。以前的函数调用像数学函数，同样的输入永远同样的输出；现在 next(t) 调两次给你两个不同的答案，因为 t 里藏着一个会变的位置。CS 61A 到这里正式从「函数式」转向「有状态的计算」，后面的面向对象（OOP）都是这一步的延伸。

做之前该掌握什么

你需要能熟练读写 while 循环和列表下标，理解递归的「相信小问题已经解决」的思路（Lab 3 / Lab 4 练过），并且能画基本的环境图。如果 for element in s 和 for i in range(len(s)) 的区别在你脑子里还不清晰，先回去把 Lab 3 的序列部分过一遍——本次的 Q2 恰好是一道不能用 for element in s 写的题，理由就藏在这个区别里。

from __future__ import annotations  # 让 list[int] 这类标注在旧版本 Python 上也能用
from typing import Iterator         # Iterator[int]：一个产出整数的迭代器

1. WWPD：List-Mutation

命令：python3 ok -q list-mutation -u。这道题不写代码，只回答「Python 会显示什么」。它的价值在于：每一行都在考一个具体的可变性规则，答错哪一行，就说明哪条规则你还没建立。

题目要什么

给出一串交互式解释器（REPL）里的语句，逐条说出 Python 会在屏幕上打印什么。规则：什么都不显示写 Nothing，报错写 Error，是函数对象写 Function。

要点在于分清三件事：

1. 这一行有没有返回值。在 REPL 里，只有表达式的值不是 None 时才会被回显。s.append(6) 返回 None，所以单独一行写它什么都不显示；但 print(s.append(6)) 会把这个 None 打出来。
2. 这一行改没改列表。改了，后面所有指向同一个列表的名字都跟着变。
3. 这一行造没造新列表。s[:] 造新的，s 赋值给别的名字不造新的。

怎么想到的

不要一行一行「猜」，要在纸上维护一张对象表：画出堆里有哪几个列表对象，每个对象当前内容是什么，然后画出每个名字的箭头指向哪个对象。每读一行，只做两种更新之一：改某个对象的内容，或改某个箭头的指向。这两件事永远不会同时发生（除非一行里有多个操作）。

初学者最常见的失误是把「赋值」和「变异」搞混。记住这条判据：

逐行推演

>>> s = [6, 7, 8]
>>> print(s.append(6))
None

s.append(6) 把 6 追加到列表尾部，然后返回 None。print 收到 None，把字符串 None 打到屏幕上。注意这里打印出 None 恰恰是因为 append 有副作用而无返回值——这是 Python 变异方法的统一约定：不要在返回值上做文章，改完就完了。

>>> s
[6, 7, 8, 6]

验证副作用确实生效了。列表对象现在是 [6, 7, 8, 6]。

>>> s.insert(0, 9)
>>> s
[9, 6, 7, 8, 6]

insert(i, elem) 把 elem 塞到下标 i 的位置，原来 i 及其后的元素全部往后挪一格。它不替换任何元素，只是插入，所以列表长度加一。insert 同样返回 None，所以单独写这一行屏幕上什么都不显示（题目要求写 Nothing 的那种情况）。

>>> x = s.pop(1)
>>> s
[9, 7, 8, 6]

pop(1) 删掉下标 1 的元素并把它返回。当前列表是 [9, 6, 7, 8, 6]，下标 1 是 6，所以 x 绑定到 6，列表剩 [9, 7, 8, 6]。pop 是列表变异方法里唯一有意义返回值的那个，记住这个例外。

>>> s.remove(x)
>>> s
[9, 7, 8]

x 是 6，remove(6) 删掉第一个等于 6 的元素。当前列表 [9, 7, 8, 6] 里只有末尾一个 6，删掉得 [9, 7, 8]。如果列表里没有这个值，remove 会抛 ValueError: list.remove(x): x not in list。

>>> a, b = s, s[:]
>>> a is s
True
>>> b == s
True
>>> b is s
False

这是整道题的核心三行。a = s 只是给同一个列表对象起了第二个名字，箭头指向同一处，所以 a is s 为 True。s[:] 是切片，切片总是造一个新列表，内容逐个复制过来。所以 b 的内容和 s 一样（b == s 为 True），但它是另一个对象（b is s 为 False）。

堆里的对象：
  对象 #1: [9, 7, 8]     <-- s 指向它, a 也指向它
  对象 #2: [9, 7, 8]     <-- b 指向它（s[:] 新造的）

名字表（全局帧）：
  s -> #1
  a -> #1
  b -> #2
  x -> 6

>>> a.pop()
8
>>> a + b
[9, 7, 9, 7, 8]

a.pop() 不带参数时弹出最后一个元素，返回 8，屏幕显示 8。关键是：a 和 s 指着同一个对象 #1，所以现在 s 也变成了 [9, 7]。而 b 指着对象 #2，完全没受影响，还是 [9, 7, 8]。

于是 a + b 是 [9, 7] + [9, 7, 8]，得到 [9, 7, 9, 7, 8]。注意 + 是造新列表的操作，它不改变 a 也不改变 b。

>>> s = [3]
>>> s.extend([4, 5])
>>> s
[3, 4, 5]
>>> a
[9, 7]

s = [3] 是重新绑定：把名字 s 的箭头改指到一个全新的列表 [3]。对象 #1 并没有消失，也没有被改动，a 还指着它。所以问 a 的值，答案仍是 [9, 7]。

这一步是很多人翻车的地方：以为 s = [3] 会「清空」a。不会。赋值只碰名字，不碰对象。

extend([4, 5]) 把可迭代对象里的元素逐个追加到尾部，所以是 [3, 4, 5] 而不是 [3, [4, 5]]。这正是 extend 和 append 的分界：append 把参数当成一个元素塞进去，extend 把参数拆开塞进去。

最后一行：整道题的高潮

>>> s.extend([s.append(9), s.append(10)])
>>> s
[3, 4, 5, 9, 10, None, None]

这一行把「求值顺序」和「副作用」拧在一起，必须严格按 Python 的求值规则一步步走。当前 s 是 [3, 4, 5]。

答案 [3, 4, 5, 9, 10, None, None] 里，9 和 10 来自参数求值时的副作用，两个 None 来自 append 的返回值。这一行同时演示了本课最重要的两条规则：参数在函数调用之前就被完整求值，以及变异方法返回 None。

2. Insert Items

题目要什么

def insert_items(s: list[int], before: int, after: int) -> list[int]:
    """Insert after into s following each occurrence of before and then return s.
    """

翻译成人话：扫描列表 s，每碰到一个值等于 before 的元素，就在它后面紧挨着插入一个 after。全部插完，把 s 本身返回。

题面有两条硬约束，它们才是这道题的真正考点：

1. 不许创建新列表（"No new lists should be created"）。所以 return 一个新拼出来的列表是不合格的，必须在原对象上就地修改。doctest 里的 new_s is test_s → True 和 large_s3 is large_s → True 就是在查这一点。
2. before == after 时不能死循环。题面明确警告：如果你的代码跑几秒还没结束，那就是陷进了「插入的新元素又被认成 before，于是再插一个」的无限循环。

看 doctest 里最刁的两行：

>>> large_s = [1, 4, 8]
>>> large_s2 = insert_items(large_s, 4, 4)
>>> large_s2
[1, 4, 4, 8]

before 和 after 都是 4。正确行为是：原列表里本来就存在的那一个 4 后面插一个 4，结果是 [1, 4, 4, 8]。新插进去的那个 4 不该再触发一次插入。这行的存在就是为了逼你处理死循环。

>>> large_s3 = insert_items(large_s2, 4, 6)
>>> large_s3
[1, 4, 6, 4, 6, 8]
>>> large_s3 is large_s
True

最后一行尤其值得琢磨：large_s3 is large_s 为 True。large_s、large_s2、large_s3 从头到尾是同一个列表对象的三个名字。因为函数返回的就是传进来的 s，而 s 就是那个对象。这条 doctest 是在验证「你确实没造新列表」。

怎么想到的

第一个念头：用 for 遍历，边遍历边插。

for i in range(len(s)):        # 这是错的
    if s[i] == before:
        s.insert(i + 1, after)

这个念头崩得很快，而且崩的方式有两种：

崩法一：range(len(s)) 在循环开始时就固定了。range 的上界在进入 for 之前算好，是原始长度。但每插入一个元素，列表就变长一格，后面的元素全部往右挪。于是 i 走到的位置和实际元素对不上，插入位置全乱。用 [1, 5, 8, 5, 2, 3] 试：range(6)，i=1 时 s[1]==5，插入后 s 变成 [1, 5, 7, 8, 5, 2, 3]；i=2 现在指着 7，不等于 5，跳过；i=3 指着 8，跳过；i=4 指着 5，插入 → [1, 5, 7, 8, 5, 7, 2, 3]；i=5 指着 7；然后循环结束了——但列表已经有 8 个元素，最后两个 2, 3 根本没被检查。这次凑巧答案对了，但只是运气。

崩法二：before == after 时无限循环。如果换成 for element in s 这种直接迭代对象的写法，Python 的列表迭代器是按下标推进的，你不断在当前位置后面插入相同的值，迭代器每往前一步都会遇到一个新插入的、又等于 before 的元素，于是永远走不到头，列表无限增长直到内存耗尽。

第二个念头：既然长度在变，就别用固定的 range，用 while 手动控制下标。

这是关键的思维转向。while index < len(s) 每一轮都重新计算 len(s)，所以列表变长了循环自然会多跑几轮，不会漏掉尾部元素。剩下的问题只有一个：插入之后 index 该往前走几格？

这一步 index += 2 一箭双雕：既避免了重复检查新元素造成的死循环，又保证了每个「原有元素」恰好被检查一次。你不需要为 before == after 写任何特判——统一的 += 2 自动处理了它。这是好解法的标志：特殊情况被结构消化掉了，而不是靠 if 打补丁。

代码

def insert_items(s: list[int], before: int, after: int) -> list[int]:
    """Insert after into s following each occurrence of before and then return s.

    >>> test_s = [1, 5, 8, 5, 2, 3]
    >>> new_s = insert_items(test_s, 5, 7)
    >>> new_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> test_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> new_s is test_s
    True
    >>> double_s = [1, 2, 1, 2, 3, 3]
    >>> double_s = insert_items(double_s, 3, 4)
    >>> double_s
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_s = [1, 4, 8]
    >>> large_s2 = insert_items(large_s, 4, 4)
    >>> large_s2
    [1, 4, 4, 8]
    >>> large_s3 = insert_items(large_s2, 4, 6)
    >>> large_s3
    [1, 4, 6, 4, 6, 8]
    >>> large_s3 is large_s
    True
    """
    # Walk through s with an explicit index so we can mutate it while scanning.
    # list.insert changes s in place, so no new list is ever created.
    index = 0
    while index < len(s):
        if s[index] == before:
            s.insert(index + 1, after)
            # Skip over the value we just inserted. This also avoids an
            # infinite loop when before == after.
            index += 2
        else:
            index += 1
    return s

逐行说明：

• index = 0：从头开始。用显式下标而不是 for element in s，因为我们需要知道「插到哪里」，也需要能主动跳格。
• while index < len(s)：每轮重新求 len(s)。这是用 while 而不是 for i in range(len(s)) 的全部理由。列表在循环体里变长，上界必须跟着变。
• if s[index] == before：用 == 比较值。题面给的类型标注是 list[int]，整数用 == 就够了；用 is 在小整数上碰巧也能过，但那是 CPython 的缓存实现细节，不能依赖。
• s.insert(index + 1, after)：在紧跟其后的位置插入。注意是 index + 1 不是 index——插在 index 会把 after 放到 before 前面。insert 是就地变异，不造新列表，满足题目约束。
• index += 2：跳过刚插入的元素。
• else: index += 1：没插入就正常前进一格。
• return s：返回同一个对象，不是 s[:] 也不是 list(s)。这样 new_s is test_s 才为 True。

验证

先追踪最普通的那条：insert_items([1, 5, 8, 5, 2, 3], 5, 7)。

与 doctest 一致。第 3 轮是关键：index 从 1 直接跳到 3，跳过了下标 2 上刚插进去的 7。

再追踪危险的那条：insert_items([1, 4, 8], 4, 4)，before 和 after 都是 4。

如果这里写的是 index += 1，第 3 轮会看到下标 2 的 4，又插一个 4，index 变 3，又看到 4……列表无限增长，程序卡死。

别名视角：三个名字一个对象

最后那组 doctest 值得单独画一下，它是本次作业「可变性」主题的浓缩。

>>> large_s = [1, 4, 8]
  堆: 对象 #A = [1, 4, 8]
  large_s -> #A

>>> large_s2 = insert_items(large_s, 4, 4)
  函数就地把 #A 改成 [1, 4, 4, 8]，然后 return s（就是 #A 本身）
  堆: 对象 #A = [1, 4, 4, 8]
  large_s  -> #A
  large_s2 -> #A        <-- 同一个对象！

>>> large_s3 = insert_items(large_s2, 4, 6)
  再次就地修改 #A: 两个 4 后面各插一个 6
  堆: 对象 #A = [1, 4, 6, 4, 6, 8]
  large_s  -> #A
  large_s2 -> #A
  large_s3 -> #A

>>> large_s3 is large_s
  两边都是 #A  =>  True
>>> large_s
  [1, 4, 6, 4, 6, 8]    <-- large_s 也「变了」，虽然从没直接赋值给它

注意第二次调用的输入是 [1, 4, 4, 8]，两个 4 都要处理。追踪一遍：index=1 时 s[1]=4，插入 6 得 [1, 4, 6, 4, 8]，index 跳到 3；index=3 时 s[3]=4，插入 6 得 [1, 4, 6, 4, 6, 8]，index 跳到 5；index=5 时 s[5]=8，不等，index=6；6 < 6 为假，退出。得 [1, 4, 6, 4, 6, 8]，与 doctest 一致。

result = []
for element in s:
    result.append(element)
    if element == before:
        result.append(after)
return result

3. Group By

题目要什么

>>> group_by([12, 23, 14, 45], lambda p: p // 10)
{1: [12, 14], 2: [23], 4: [45]}
>>> group_by(range(-3, 4), lambda x: x * x)
{9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}

给一个序列 s 和一个函数 fn，把 s 里的元素按 fn(e) 的结果分堆，返回一个字典：键是某个 fn(e) 的值，值是所有算出这个键的元素组成的列表。

第一个 doctest 里，fn 是「取十位数」：12 // 10 = 1，23 // 10 = 2，14 // 10 = 1，45 // 10 = 4。所以 12 和 14 同属键 1，各自的 23 和 45 单独成组。

第二个 doctest 里，fn 是平方：-3 和 3 都算出 9，所以它们归到同一个键下。这也说明 fn 完全可以是多对一的——分组的意义正在于此。

有两个细节是 doctest 在无声地要求的：

• 字典的键的出现顺序：Python 3.7 起字典保持插入顺序，而 doctest 是逐字符比对输出的。所以键出现的先后必须和「第一次遇到该键」的先后一致。range(-3, 4) 的遍历顺序是 -3, -2, -1, 0, 1, 2, 3，第一次遇到的键依次是 9, 4, 1, 0——正好对上 doctest 里 {9: ..., 4: ..., 1: ..., 0: ...} 的顺序。这意味着你必须按 s 的自然顺序遍历，不能先排序也不能倒着来。
• 每个列表内部的顺序：9: [-3, 3] 里 -3 在前，因为它先被遍历到。所以新元素要 append 到列表尾部，不能 insert(0, ...)。
• s 不一定是列表：第二个 doctest 传的是 range(-3, 4)。所以别用 s.append 之类的列表方法去碰 s，只能遍历它。

怎么想到的

这道题给了骨架，填空即可：

grouped = {}
for ____ in ____:
    key = ____
    if key in grouped:
        ____
    else:
        grouped[key] = ____
return grouped

骨架已经把思路暴露了：建一个空字典，遍历所有元素，每个元素算出它的键，然后把它塞进对应的那个列表里。这个「累积器（accumulator）」模式在 CS 61A 反复出现——先造一个空容器，边遍历边往里加，最后返回它。

唯一需要动脑的是 if key in grouped 这个分支为什么必须存在。

第一个念头：直接写 grouped[key].append(element)。这在键已经存在时完全正确，但第一次遇到某个键时，grouped[key] 会抛：

KeyError: 1

因为字典里根本没有键 1，取不到值就没法调 append。这就是分支存在的理由：第一次遇到一个键，需要先给它建一个列表；之后再遇到，才能往已有的列表里追加。

第二个念头：那就每次都写 grouped[key] = grouped.get(key, []) + [element]。这样确实能避开分支，但每次都在造一个新列表（+ 是拼接），元素多了会很慢——把 \(n\) 个元素塞进同一个键，总共复制的元素数是 \(1 + 2 + \dots + n\)，也就是 \(\Theta(n^2)\)。而 append 是均摊 \(\Theta(1)\)，整体 \(\Theta(n)\)。骨架给的写法是对的。

代码

def group_by(s: list[int], fn) -> dict[int, list[int]]:
    """Return a dictionary of lists that together contain the elements of s.
    The key for each list is the value that fn returns when called on any of the
    values of that list.

    >>> group_by([12, 23, 14, 45], lambda p: p // 10)
    {1: [12, 14], 2: [23], 4: [45]}
    >>> group_by(range(-3, 4), lambda x: x * x)
    {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}
    """
    grouped = {}
    for element in s:
        key = fn(element)
        if key in grouped:
            grouped[key].append(element)
        else:
            grouped[key] = [element]
    return grouped

逐行说明：

• grouped = {}：空字典作为累积器。它在整个函数里是同一个对象，被不断就地修改——这正是本次作业「可变性」主题的正面应用：可变数据让「逐步构建一个结果」变得自然而高效。
• for element in s：直接迭代 s 的元素，而不是下标。这里不需要下标（不涉及插入位置），而且 s 可能是 range，直接迭代对 range、列表、元组、字符串都通用。
• key = fn(element)：调用传进来的函数算出键。这是高阶函数（higher-order function）的典型用法——group_by 自己不关心怎么分组，把「分组规则」外包给调用者。同一个 group_by 可以按十位数分、按平方分、按奇偶分。
• if key in grouped：字典的 in 检查的是键，不是值。这一点和列表不同：x in [1, 2, 3] 查元素，x in {1: 'a'} 查键。
• grouped[key].append(element)：先取出已有的列表，再就地追加。这行是变异而不是赋值——它没有改字典里键 key 对应的箭头（还指着同一个列表对象），只改了那个列表对象的内容。
• grouped[key] = [element]：新建一个单元素列表并挂到字典上。这行是字典的项赋值，属于字典的变异操作。
• return grouped：返回这个字典。

验证

手动追踪 group_by([12, 23, 14, 45], lambda p: p // 10)。

返回 {1: [12, 14], 2: [23], 4: [45]}，与 doctest 逐字符一致：键的顺序是 1、2、4，因为它们的首次出现顺序就是这个；[12, 14] 里 12 在前，因为 append 加到尾部。

第三轮尤其值得看清楚它在对象层面发生了什么：

第 2 轮结束后：
  堆: 字典对象 #D = {1 -> #L1, 2 -> #L2}
      列表对象 #L1 = [12]
      列表对象 #L2 = [23]
  grouped -> #D

第 3 轮 grouped[1].append(14):
  step 1: 求 grouped[1]  =>  拿到 #L1 这个列表对象
  step 2: 对 #L1 调 append(14)  =>  #L1 就地变成 [12, 14]
  字典 #D 里键 1 的箭头一动没动，仍然指向 #L1
  堆: 字典对象 #D = {1 -> #L1, 2 -> #L2}
      列表对象 #L1 = [12, 14]   <-- 内容变了
      列表对象 #L2 = [23]

这是「变异 vs 重新绑定」在字典上的又一次体现：grouped[1].append(14) 改的是列表对象，grouped[1] = [12, 14] 改的是字典里的箭头。这次两种写法的最终结果一样，但含义完全不同——如果别处还有名字指着 #L1，前者会影响它，后者不会。

再验第二条 doctest：group_by(range(-3, 4), lambda x: x * x)。遍历顺序 -3, -2, -1, 0, 1, 2, 3，键依次是 9, 4, 1, 0, 1, 4, 9。前四个都是新键，按 9, 4, 1, 0 的顺序插入；后三个 1, 4, 9 都已存在，分别 append 到对应列表。最终 {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}——键的顺序是 9、4、1、0，与 doctest 一致。这也说明：如果你把遍历改成 for element in sorted(s)，键的顺序会变成 9、4、1、0 之外的东西，doctest 会挂，尽管「分组」在数学上是一样的。

4. WWPD：Iterators

命令：python3 ok -q iterators-wwpd -u。三组题，分别考「iterable 与 iterator 的分野」「for 循环会耗尽迭代器」「map/filter/zip 是惰性的」。答案在本仓库 labs/lab05/tests/iterators-wwpd.py 里，已解锁为明文并通过哈希校验。

先把两个概念钉死

最后一行是全部困惑的解药：迭代器也是可迭代对象（所有 iterator 都是 iterable），但反过来不成立。而对迭代器调 iter，Python 规定必须返回它自己，不能重置。这条规定让「for 循环内部先调 iter」这件事对迭代器和列表都能工作，代价是 for 循环会消费掉迭代器的状态。

第一组：iter 造的是谁

>>> s = [1, 2, 3, 4]
>>> t = iter(s)
>>> next(s)
Error

s 是列表，是 iterable 但不是 iterator。对它调 next 报 TypeError: 'list' object is not an iterator。WWPD 的答题规则里这算 Error。

为什么 Python 要这样设计？因为如果列表自己就是迭代器，它就得自己记一个「当前位置」，那么两段代码同时遍历同一个列表就会互相干扰。把「容器」和「遍历进度」分成两个对象，是这个设计的全部意义。

>>> next(t)
1
>>> next(t)
2

t 是迭代器，每调一次 next 往前一格。现在 t 的内部位置停在「已经吐出了 1 和 2」。

>>> next(iter(s))
1
>>> next(iter(s))
1

这两行是本组的考点。iter(s) 对列表 s 调用，每次都造一个全新的迭代器，从头开始。所以两次都吐出 1。而且这两个临时迭代器用完就被丢弃了（没有名字指着它们），完全不影响 t。

此刻堆里的对象：
  列表 #S = [1, 2, 3, 4]        （从头到尾没变过）
  迭代器 #T  -> #S, 位置=2       （t 指着它，已吐出 1, 2）
  迭代器 #tmp1 -> #S, 位置=1     （第一个 iter(s)，吐完 1 就没人引用了）
  迭代器 #tmp2 -> #S, 位置=1     （第二个 iter(s)，同上）

名字表：
  s -> #S
  t -> #T

官方网页版这里还多两行：

>>> u = t
>>> next(u)
3
>>> next(t)
4

u = t 不造新迭代器，只是给 #T 起了第二个名字——和 Q1 里 a = s 完全同构的别名现象，只不过这次被别名的是一个有状态的迭代器。next(u) 推进的是 #T，吐出 3；接着 next(t) 从 #T 继续，吐出 4。它们共享同一个进度。

（本仓库 tests/iterators-wwpd.py 里的版本省掉了 u = t，直接连着写 next(t) → 3、next(t) → 4。结果一样，因为 u 本来就是 t。）

第二组：for 循环吃掉了迭代器

>>> r = range(6)
>>> r_iter = iter(r)
>>> next(r_iter)
0

range(6) 代表 0 到 5。它是 iterable 不是 iterator（next(range(6)) 会报错）。iter(r) 造出迭代器，第一次 next 给 0。现在 r_iter 的剩余序列是 1, 2, 3, 4, 5。

>>> [x + 1 for x in r]
[1, 2, 3, 4, 5, 6]

列表推导式遍历的是 r——那个 range 对象本身，不是 r_iter。推导式内部会对 r 调一次 iter，得到一个全新的迭代器，从 0 走到 5。所以结果是 [1, 2, 3, 4, 5, 6]。r_iter 的位置没有受任何影响。

>>> [x + 1 for x in r_iter]
[2, 3, 4, 5, 6]

这次遍历的是 r_iter。推导式对它调 iter，按规定返回它自己（不重置）。于是从当前位置开始走：还剩 1, 2, 3, 4, 5，加一得 [2, 3, 4, 5, 6]。注意少了一个元素——那个 0 在上上一行被 next 吃掉了，永远回不来。

>>> next(r_iter)
StopIteration

上一行的推导式把 r_iter 走到了尽头（推导式正是靠捕获 StopIteration 来知道该停的）。现在再 next，迭代器已空，抛 StopIteration。

>>> t = iter([4, 3, 2, 1])
>>> for e in t:
...     print(e)
4
3
2
1
>>> for e in t:
...     print(e)

第三组：map / filter / zip 都是惰性的

>>> map_iter = map(lambda x : x + 10, range(5))
>>> next(map_iter)
10
>>> next(map_iter)
11

Python 3 的 map 不返回列表，返回一个迭代器。调用 map(...) 的那一刻，lambda 一次都没被执行；只有 next 来了，它才去底层 range 取一个值、把 lambda 套上去、返回结果。这叫惰性求值。

底层是 range(5)，即 0,1,2,3,4。第一次 next 取 0 得 10，第二次取 1 得 11。

>>> list(map_iter)
[12, 13, 14]

list() 会把迭代器一次性抽干。剩下的底层元素是 2, 3, 4，各加 10 得 [12, 13, 14]。前面被 next 拿走的 10 和 11 不会出现在这里——这是本组最容易答错的一行，很多人会写 [10, 11, 12, 13, 14]，那是把 map 当成返回列表了。

>>> for e in filter(lambda x : x % 4 == 0, range(1000, 1008)):
...     print(e)
1000
1004

filter(f, s) 也返回迭代器，只放行 f(x) 为真的元素。range(1000, 1008) 是 1000, 1001, ..., 1007（不含 1008）。哪些能被 4 整除？1000 % 4 == 0 成立（1000 = 4 × 250），1004 % 4 == 0 成立。1001, 1002, 1003, 1005, 1006, 1007 都不行。所以打印两行：1000 和 1004。

注意这里是 print(e)，所以每个值单独一行，没有引号也没有方括号——这是「REPL 回显」和「print 输出」的区别，也是 WWPD 常考的点。

>>> [x + y for x, y in zip([1, 2, 3], [4, 5, 6])]
[5, 7, 9]

zip 把多个可迭代对象「拉链式」配对，每次 next 从每个参数各取一个，打包成元组。这里依次产出 (1, 4)、(2, 5)、(3, 6)。

for x, y in ... 是解包（unpacking）：把每个元组的两个分量分别绑到 x 和 y。于是三轮分别算 1+4=5、2+5=7、3+6=9，得 [5, 7, 9]。

如果两个序列长度不等，zip 在最短的那个用完时就停止。

5. Count Occurrences

题目要什么

给一个迭代器 t、一个整数 n、一个值 x，数出 t 的前 n 个元素里有几个等于 x。可以假设 t 至少有 n 个元素。

题面有一条极其重要的约束：

You should call next on t exactly n times.

必须恰好调用 next 共 n 次。不能多也不能少。为什么这条约束是硬性的？因为迭代器有状态，多调一次 next 就永久地吃掉了一个元素，调用者后面拿不回来。看 doctest 是怎么抓这件事的：

>>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
>>> count_occurrences(u, 1, 3)  # Only iterate over 3
1
>>> count_occurrences(u, 3, 2)  # Only iterate over 2, 2, 2
3
>>> list(u)                     # Ensure that the iterator has advanced the right amount
[1, 2, 1, 4, 4, 5, 5, 5]

同一个迭代器 u 被连续调用两次，第二次从第一次停下的地方继续。第一次 n=1，只吃掉 3；第二次 n=3，吃掉 2, 2, 2。累计吃掉 4 个元素，所以 list(u) 应该正好是剩下的 8 个：[1, 2, 1, 4, 4, 5, 5, 5]。

如果你的实现多调了一次 next，list(u) 就会少一个元素，这条 doctest 立刻挂掉。这就是题目验证「恰好 n 次」的手段——用调用者能观察到的副作用来验证。

还有一条边界值得注意：

>>> v = iter([4, 1, 6, 6, 7, 7, 6, 6, 2, 2, 2, 5])
>>> count_occurrences(v, 6, 6)
2

前 6 个元素是 4, 1, 6, 6, 7, 7，其中等于 6 的有 2 个。后面下标 6、7 那两个 6 不算，因为它们超出了前 n 个的范围。这条在提醒你：n 限制的是看多少个元素，不是「数到 n 个匹配就停」。

怎么想到的

第一个念头：用 for 遍历 t，配一个计数器，够 n 个就 break。

count = 0
seen = 0
for element in t:          # 这是错的
    if element == x:
        count += 1
    seen += 1
    if seen == n:
        break
return count

这个写法的答案是对的，break 也确实在第 n 个元素之后跳出。它看起来 next 恰好被调了 n 次。但它把简单的事写复杂了：需要两个计数器，还要在循环体里手动判断退出。而且它有个隐蔽的坑——如果 n = 0，for 会先从 t 取一个元素才发现要 break，多吃了一个。（本题 doctest 没有 n=0，但这个思考方向是对的。）

第二个念头（更糟）：把 t 转成列表再切片。

lst = list(t)[:n]          # 这是错的
return lst.count(x)

list(t) 会把整个迭代器抽干。count_occurrences(u, 1, 3) 之后 u 就空了，第二次调用 count_occurrences(u, 3, 2) 立刻抛 StopIteration，list(u) 更是返回 []。题面警告"If you need to iterate through more than n elements, think about how you can optimize your solution"，说的就是这个。

转折点：把问题倒过来看。与其「遍历 t，数够 n 个就停」，不如「循环 n 次，每次主动从 t 里取一个」。

这个转换是本题的全部智慧所在：不要让迭代器驱动循环，让计数驱动循环，把迭代器当成一个「取值的水龙头」。迭代器提供数据，range(n) 提供节奏。两者解耦之后，代码短了一半，正确性也一眼可见。

顺带说一句 _ 这个名字。它是 Python 的约定，表示「这个变量我不用」。这里循环变量确实没用——我们只关心循环跑几次，不关心当前是第几次。用 _ 是在向读代码的人说明这一点。

代码

def count_occurrences(t: Iterator[int], n: int, x: int) -> int:
    """Return the number of times that x is equal to one of the
    first n elements of iterator t.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s, 10, 9)
    3
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(t, 3, 10)
    2
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> count_occurrences(u, 1, 3)  # Only iterate over 3
    1
    >>> count_occurrences(u, 3, 2)  # Only iterate over 2, 2, 2
    3
    >>> list(u)                     # Ensure that the iterator has advanced the right amount
    [1, 2, 1, 4, 4, 5, 5, 5]
    >>> v = iter([4, 1, 6, 6, 7, 7, 6, 6, 2, 2, 2, 5])
    >>> count_occurrences(v, 6, 6)
    2
    """
    # Call next exactly n times: once per iteration of this loop.
    count = 0
    for _ in range(n):
        if next(t) == x:
            count += 1
    return count

逐行说明：

• count = 0：累积器，从 0 开始数。
• for _ in range(n)：循环恰好 n 轮。range(n) 在 n = 0 时是空的，一轮都不跑，next 一次都不调，返回 0——边界自动正确，不需要特判。
• if next(t) == x：每轮调用 next(t) 恰好一次。这个位置很关键：next(t) 直接写在条件里，不管条件成不成立它都被求值了一次。如果写成 if x == next(t) 也一样。但绝不能写成 if next(t) == x or next(t) == y 这种——短路求值会让 next 的调用次数变得不确定。
• count += 1：匹配上就加一。
• return count：循环跑完 n 轮才返回。注意 return 在循环外面——写在里面会导致第一轮就返回。

为什么用 == 而不是 is？因为要比的是值相等。对小整数 CPython 会缓存对象，is 碰巧也能过；但一旦元素超过 256，is 就会失败。永远用 == 比较值。

验证

追踪 doctest 里最能说明问题的那一组：同一个迭代器被调两次。

>>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])

把 12 个元素的账算清楚：原始 12 个，第一次调用消费 1 个，第二次消费 3 个，共 4 个，剩 8 个。list(u) 拿到的正好是 8 个。这个账只有在 next 被恰好调用 n 次时才对得上——这就是 doctest 用 list(u) 收尾的用意。

再看第一条 doctest，count_occurrences(s, 10, 9)，s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])：

n = 10 正好等于列表长度，10 轮全部走完，返回 3。next 恰好被调了 10 次，迭代器不多不少地被抽干——如果实现里多了第 11 次调用，这里就会抛 StopIteration。这也解释了题面为什么说「可以假设 t 至少有 n 个元素」：正因为恰好取 n 个，所以不必担心中途没货。

for _ in range(n):
    if next(t) == x:
        count += 1
    return count      # 错：第一轮就返回了

6. Generate Permutations

题目要什么

实现 perms：一个生成器函数，接收一个序列 seq，逐个产出 seq 的全部排列（permutation）。每个排列是一个列表，装着 seq 的全部元素但顺序不同。产出顺序任意。题面说可以假设 seq 不为空。

>>> p = perms([100])
>>> type(p)
<class 'generator'>
>>> next(p)
[100]
>>> try: # Prints "No more permutations!" if calling next would cause an error
...     next(p)
... except StopIteration:
...     print('No more permutations!')
No more permutations!
>>> sorted(perms([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(perms((10, 20, 30)))
[[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
>>> sorted(perms("ab"))
[['a', 'b'], ['b', 'a']]

从 doctest 里能读出四条硬要求：

1. type(p) 必须是 <class 'generator'>。所以函数体里必须有 yield，不能先攒一个列表再 return。
2. 产出的必须是 list，不是元组也不是字符串。sorted(perms((10, 20, 30))) 期望的是 [[10, 20, 30], ...]——输入是元组，输出仍是列表的列表。sorted(perms("ab")) 期望 [['a', 'b'], ['b', 'a']]——输入是字符串，输出是字符列表。输入类型不影响输出类型。
3. 数量必须正好是 \(n!\)，不重不漏。3 个元素 6 个排列，多一个少一个 sorted 的结果都对不上。
4. 耗尽后抛 StopIteration。这是生成器函数体执行完自然就会发生的，不需要你写任何东西。

用 sorted 包一层是题目的贴心之处：它把「任意顺序」变成了确定的顺序，这样 doctest 才能比对。sorted 接收任何可迭代对象（生成器当然可以），返回排好序的列表。列表之间的比较是逐元素字典序，所以 [1, 2, 3] < [1, 3, 2] < [2, 1, 3]。

怎么想到的

先别想生成器，先想「怎么枚举全排列」。这两件事是分开的：先把递归结构想清楚，再考虑怎么用 yield 表达。混在一起想是初学者卡住的主要原因。

第一步：找到递归结构

递归的标准套路是「假设小一号的问题已经解决了，怎么用它拼出大问题的答案」。这里的「小一号」自然的选法是：把第一个元素拿掉，剩下的元素的全排列我已经会算了。

比如要算 perms([1, 2, 3])。假设我已经有了 perms([2, 3]) 的结果：[2, 3] 和 [3, 2]。现在要把 1 加回去。加在哪？

对 [2, 3] 这个长度为 2 的列表，1 可以插在三个位置：最前面、中间、最后面。

smaller = [2, 3]，把 first = 1 插进去：
  位置 0:  [1] + [2, 3]       ->  [1, 2, 3]
  位置 1:  [2] + [1] + [3]    ->  [2, 1, 3]
  位置 2:  [2, 3] + [1]       ->  [2, 3, 1]

smaller = [3, 2]，把 first = 1 插进去：
  位置 0:  [1, 3, 2]
  位置 1:  [3, 1, 2]
  位置 2:  [3, 2, 1]

一共 2 × 3 = 6 个，正好是 3! = 6。

这就是全部的算法。每个长度为 k 的排列，可以插入的位置有 k + 1 个（k 个元素之间有 k-1 个缝，再加上头和尾）。所以数量关系是 \((k+1)! = k! \times (k+1)\)——递归结构和阶乘的递推式完全同构，这是它不重不漏的证据。

为什么不重复？因为每个最终排列里 first 的位置是唯一确定的：把 first 抠掉之后剩下的东西就是那个 smaller，而 first 所在的下标就是那个 position。(smaller, position) 这一对唯一决定一个结果，反之亦然，是个双射。

第二步：base case 该是什么

这里我走了一点弯路。最先想到的 base case 是 len(seq) == 1：只有一个元素时，唯一的排列就是它自己，yield [seq[0]]。这是对的，题面也说了 seq 不为空，所以够用。

但更干净的是 len(seq) == 0：空序列有且仅有一个排列，就是空列表。这句话第一次听会觉得别扭——「什么都没有，怎么还有一种排法？」——但它是对的：\(0! = 1\)。把空列表当成一个合法的排列，递归就能一路收到底，不需要在长度 1 处停下。

第三步：翻译成生成器

如果写成普通函数，会是这样（示意，不是提交的代码）：

def perms_list(seq):          # 返回列表的版本，用来对照
    if len(seq) == 0:
        return [[]]
    result = []
    first, rest = seq[0], seq[1:]
    for smaller in perms_list(rest):
        for position in range(len(smaller) + 1):
            result.append(smaller[:position] + [first] + smaller[position:])
    return result

改成生成器只需要两处改动：

• 把 result.append(X) 换成 yield X——不再攒起来，算一个吐一个。
• 把 return [[]] 换成 yield []——base case 也只吐一个值。
• 顺带把 result = [] 和 return result 删掉，它们没用了。

然后是最容易卡住的一点：for smaller in perms(rest) 里，perms(rest) 是一个生成器对象，能直接放进 for 吗？

能。因为生成器就是迭代器，迭代器都是可迭代的。for 会对它调 iter（返回它自己），然后不断 next，直到 StopIteration。题面的 Hint 特意点了这句："Remember, it's possible to loop over generator objects because generators are iterators!"

这一点非常重要，因为它意味着递归生成器的写法和递归普通函数几乎一模一样：你照样写 for x in 递归调用(...)，Python 自动帮你把内层生成器的值一个个抽出来。

代码

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

    >>> p = perms([100])
    >>> type(p)
    <class 'generator'>
    >>> next(p)
    [100]
    >>> try: # Prints "No more permutations!" if calling next would cause an error
    ...     next(p)
    ... except StopIteration:
    ...     print('No more permutations!')
    No more permutations!
    >>> sorted(perms([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(perms((10, 20, 30)))
    [[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
    >>> sorted(perms("ab"))
    [['a', 'b'], ['b', 'a']]
    """
    if len(seq) == 0:
        # There is exactly one arrangement of nothing: the empty list.
        yield []
    else:
        first, rest = seq[0], seq[1:]
        # Every permutation of seq is some permutation of the remaining
        # elements with `first` spliced back in at one of its positions.
        for smaller in perms(rest):
            for position in range(len(smaller) + 1):
                yield smaller[:position] + [first] + smaller[position:]

逐行说明：

• if len(seq) == 0：base case。用 len(seq) == 0 而不是 seq == []，因为 seq 可能是元组或字符串，() == [] 是 False，那样会漏掉 base case 导致无限递归。len 对三种类型都工作。
• yield []：吐出一个空列表。注意是 yield 不是 return。如果写 return [[]]，函数依然是生成器（因为别处有 yield），但 return 在生成器里的含义是「结束迭代」，返回值不会被 yield 出来，上层的 for smaller in perms(rest) 会一个值都拿不到，最终 perms 什么都不产出。
• first, rest = seq[0], seq[1:]：拆出第一个元素和剩余部分。seq[0] 对列表得元素、对元组得元素、对字符串得单个字符；seq[1:] 保持原类型（列表切片得列表，字符串切片得字符串）。这没关系，因为 rest 只被拿去递归和求 len，而最终拼出的结果一定是列表——见下一条。
• for smaller in perms(rest)：递归。perms(rest) 返回一个生成器对象；for 逐个把它产出的排列拿出来绑给 smaller。关键：smaller 一定是列表，因为 base case 吐的是 []，而每层拼出来的 list + list + list 也是列表。类型在 base case 处就被「统一」成了列表，不管输入是什么类型。这正是 sorted(perms("ab")) 得到 [['a', 'b'], ['b', 'a']] 而不是 ['ab', 'ba'] 的原因。
• for position in range(len(smaller) + 1)：+ 1 是这行的灵魂。长度为 k 的列表有 k + 1 个可插入位置（下标 0 到 k）。写成 range(len(smaller)) 会漏掉「插到最后面」这一种，结果数量不对（少一大批）。
• yield smaller[:position] + [first] + smaller[position:]：切开、插入、拼接。smaller[:position] 是插入点之前的部分，[first] 把 first 包成单元素列表（不包的话 list + int 会报 TypeError），smaller[position:] 是插入点之后的部分。三段拼起来是一个全新的列表——+ 不改动 smaller，所以下一轮 position 用的还是原封不动的 smaller。

验证

把 perms([1, 2, 3]) 的调用栈真的展开。

注意产出的原始顺序（[1,2,3], [2,1,3], [2,3,1], [1,3,2], ...）看起来毫无规律——这正是题面说「permutations may be yielded in any order」的原因，也是 doctest 必须套 sorted 的原因。

生成器的执行时机：这才是本题的重点

上面的展开有个容易被忽略的地方：这六个排列不是一次算完的。递归调用 perms(rest) 只是造了一个生成器对象，函数体一行都没执行。真正的计算是被外面的 next 一点点「拉」出来的。

看第一条 doctest 就明白了：

这里有个漂亮的细节：整条递归链上的每一层生成器都同时「冻结」在自己的 yield 处。perms([1,2,3]) 求值时，内存里同时存在 4 个生成器对象（层 0 到层 3），每个都记着自己的局部变量（first、rest、smaller、position）和「执行到第几行」。next 一来，最外层解冻，可能会向内层要一个值，内层解冻……像一串多米诺骨牌反向传递。

另一种写法：yield from

题面介绍了 yield from，它把一个可迭代对象里的值全部 yield 出去。本题的解法里其实用不上它（因为每个值都要经过加工，不是原样转发），但值得知道两种写法的分界：

本题属于第二种：拿到 smaller 之后还要插入 first，而且一个 smaller 要变出 k+1 个结果，所以只能用 for + yield。硬要用 yield from 也可以，把内层循环写成生成器表达式：yield from (smaller[:i] + [first] + smaller[i:] for i in range(len(smaller) + 1))——但这可读性更差，不推荐。

7. Repeated（选做）

题面把这题标成 Optional，不做也能拿 lab 学分。但它是 count_occurrences 的自然升级，而且「最少调用 next」这个约束比上一题更难满足，很值得做。本仓库的 labs/lab05/lab05.py 里已实现并通过 ok。

题目要什么

给一个迭代器 t 和整数 k（k > 1），返回 t 里第一个连续出现 k 次的值。可以假设这样的值一定存在。

>>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> repeated(s, 2)
9
>>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> repeated(t, 3)
8

同一个序列，k=2 答案是 9（下标 3、4 那两个连着的 9），k=3 答案是 8（下标 6、7、8 三个连着的 8）。注意前面也有 10 出现了三次，但不连续，不算。「连续」是这题的关键词。

硬约束：

Call next on t only the minimum number of times required. If you are receiving a StopIteration exception, your repeated function is calling next too many times.

只调用最少次数的 next。意思是：一旦连续计数达到 k，立刻返回，不许再多取一个来「确认」。看这组 doctest 就明白为什么：

>>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
>>> repeated(u, 3)
2
>>> repeated(u, 3)
5

第一次调用在读到第三个 2（下标 3）时就必须返回，此时 u 停在「下一个是下标 4 的 1」。第二次调用从那里接着读 1, 2, 1, 4, 4, 5, 5, 5，第一个连续三次的是 5，返回 5。

如果第一次调用多读了一个元素（比如为了「看看下一个还是不是 2」），那个 1 就被吃掉了。这次碰巧不影响答案，但看最后一条：

>>> v = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
>>> repeated(v, 3)
2

连续三个 2 在下标 8、9、10，读到下标 10 就该返回。序列最后还有一个 5。如果多读一个正好读到 5，虽然还没到尽头不会崩，但对 u 那组连续调用就会出错。而 repeated(u, 3) 第二次返回 5 时，5 是序列的最后一个元素——多读一次立刻 StopIteration。这就是题面警告里说的那个症状。

怎么想到的

第一个念头：把元素攒进列表，然后检查列表末尾 k 个是否全相同。

seen = []
while True:                       # 能跑，但笨重
    seen.append(next(t))
    if len(seen) >= k and len(set(seen[-k:])) == 1:
        return seen[-1]

这个能过，调用 next 的次数也是最少的。但它保存了全部历史元素，空间是 \(\Theta(n)\)，而实际上我们根本不需要记住三步之前的东西。这就引出了正确的思路。

转折：真正需要记住的只有两件事——「上一个值是什么」和「它已经连续出现了几次」。

这是一个典型的「用常数空间做流式处理」的模式。每读进一个新值 value，只需要问一个问题：它和上一个值一样吗？

• 一样 → 连续计数加一。
• 不一样 → 连续断了，重新开始：把「上一个值」换成 value，计数归 1。

然后检查计数是否达到 k，达到就返回。

初始值怎么设：一个真实的弯路

我最初把初始值写成 last_value = None、streak = 0，判断条件写 if value == last_value。这在一般情况下没问题，但有个隐患：如果迭代器里真的有 None，第一个元素就会和初始的 last_value 撞上，被错误地算成「连续第 2 次」。

本题的 doctest 全是整数，不会触发。但修法很简单，而且更能说明意图：用 streak > 0 作为「是否已经有上一个值」的标志。

if streak > 0 and value == last_value:
    streak += 1
else:
    last_value, streak = value, 1

第一轮时 streak 是 0，and 短路，不会去比较 value == last_value，直接走 else 把 last_value 设成第一个值、streak 设成 1。之后 streak 永远 ≥ 1，条件退化成纯粹的值比较。用短路求值消化掉「第一次特殊」这件事，比写 if first_iteration: ... else: ... 干净得多。

代码

def repeated(t: Iterator[int], k: int) -> int:
    """Return the first value in iterator t that appears k times in a row,
    calling next on t as few times as possible.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(t, 3)
    8
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(u, 3)
    2
    >>> repeated(u, 3)
    5
    >>> v = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(v, 3)
    2
    """
    assert k > 1
    # Track the most recent value and how many times in a row it has appeared.
    # We return as soon as the streak reaches k, so next is called the
    # minimum number of times.
    last_value = None
    streak = 0
    while True:
        value = next(t)
        if streak > 0 and value == last_value:
            streak += 1
        else:
            last_value, streak = value, 1
        if streak == k:
            return value

逐行说明：

• assert k > 1：题面骨架自带的，保证 k 至少是 2。k = 1 时「连续一次」这个说法没意义（任何元素都满足），所以直接排除。
• last_value = None、streak = 0：两个状态变量。streak = 0 特意表示「还没读到任何值」。
• while True：无限循环。没有循环条件——因为退出的唯一方式是 return。题面保证了答案存在，所以循环一定会结束。用 while True 而不是 for _ in range(...)，因为我们事先不知道要读多少个元素。
• value = next(t)：每轮恰好取一个元素。整个函数里 next 只出现在这一处，这是「调用次数最少」的结构性保证。
• if streak > 0 and value == last_value：短路保护 + 值比较。第一轮 streak 为 0，短路，不比较。
• streak += 1：连上了。
• else: last_value, streak = value, 1：断了（或者是第一轮）。同时更新两个变量——注意等号右边先整体求值，所以哪怕写成 streak, last_value = 1, value 也一样。计数设成 1 而不是 0，因为 value 本身就算连续的第一次。
• if streak == k: return value：用 == 而不是 >=。其实这里两种都对（因为一到 k 就返回了，永远不会超过），但 == 更能表达「精确地在达到的那一刻返回」。返回 value 也可以写成返回 last_value——此刻两者相等。

验证

追踪 u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5]) 上的两次连续调用。

第一次：repeated(u, 3)

返回 2。✓ 共调用 next 四次，消费了 3, 2, 2, 2。u 现在停在下标 4（值为 1）之前。

第二次：repeated(u, 3)——从 1, 2, 1, 4, 4, 5, 5, 5 继续。

返回 5。✓ 与 doctest 一致。

第 6 轮是关键：两个 4 之后来了个 5，连续断了，streak 必须归 1 而不是归 0。归 0 的话第 7、8 轮只能数到 2，永远达不到 3，函数会一直往下读直到 StopIteration。

还要注意：第 8 轮读的 5 是整个序列的最后一个元素。函数在这一刻立即返回，一次多余的 next 都没有。如果实现里在返回前还想「再确认一下」多读一个，这里立刻抛 StopIteration——这就是题面警告的场景，现在你能精确地解释它为什么会发生了。

8. 整份作业回顾

Lab 5 表面上是两个不相干的主题拼在一起（可变数据 + 迭代器/生成器），实际上它们讲的是同一件事的两面：当计算带上状态之后，你脑子里那张「名字 → 值」的表就不够用了。

三张必须同时装在脑子里的图

做 WWPD 题时，如果你只在心里默念「这行大概输出啥」，一定会错。真正有效的做法是动笔维护上面这三张图，每读一行只更新其中一处。这个习惯到后面的 OOP 和链表章节会救你很多次。

真正学到的思维方法

一条贯穿全篇的判断力

本次作业里有两处看似矛盾的要求，值得放在一起看：

• Q2 禁止造新列表，必须就地改。
• Q6 必须造新列表（smaller[:position] + [first] + smaller[position:]），不能就地改 smaller。

判据只有一条：这个对象还有没有别人要用？

Q2 里 s 就是调用者手上那个列表，调用者要的正是「我的列表被改了」这个效果，所以必须原地改。Q6 里 smaller 要在内层循环中被反复使用 k+1 次，改它就等于毁掉后面几轮的输入，所以必须每次造新的。

写代码时问自己这个问题，比死记「什么时候该用 append 什么时候该用 +」有用得多。这也是「可变性」这一章真正的教学目标：可变数据是把双刃剑，它让「逐步构建」变得高效，也让「谁改了谁」变得难以追踪。用不用它，取决于你能不能说清楚这个对象的所有权归谁。

生成器为什么值得单独学一遍

如果你觉得 perms 用普通函数攒列表也能写，为什么非要 yield——记住这三点：

1. 空间：\(n!\) 个结果一次全存 vs 任意时刻只存 \(n\) 个暂停的函数帧。
2. 时间：只要前 3 个排列，生成器就只算 3 个；列表版必须先把 \(n!\) 个全算完。
3. 能力：生成器可以描述无穷序列（比如「所有自然数」「所有素数」），列表根本写不出来。

而生成器之所以能做到这些，靠的是一个全新的执行模型：函数可以在中途暂停，把控制权交回去，之后再从暂停处继续，局部变量原样保留。这打破了你到目前为止对函数的全部直觉（调用 → 执行完 → 返回 → 帧销毁）。Q6 的调用栈展开就是在训练这个新直觉，值得反复看几遍。