07_Python工具函数

Python 工具函数

itertools.accumulate —— 前缀和 / 前缀最值

签名：itertools.accumulate(iterable, func=operator.add, *, initial=None)

一遍扫描累积出「每一步的折叠结果」，默认就是前缀和：

from itertools import accumulate
from operator import mul

a = [1, 2, 3, 4]

list(accumulate(a))             # [1, 3, 6, 10]  前缀和（默认 operator.add）
list(accumulate(a, initial=0))  # [0, 1, 3, 6, 10]  头部多一个初值（Python 3.8+）
list(accumulate(a, mul))        # [1, 2, 6, 24]  前缀积

换 func 得到前缀最值——竞赛里最常用的形态：

b = [3, 1, 4, 1, 5]

list(accumulate(b, min))  # [3, 1, 1, 1, 1]  前缀最小
list(accumulate(b, max))  # [3, 3, 4, 4, 5]  前缀最大

后缀数组技巧：先反转、累积、再反转回来：

# 后缀最大：suf_max[i] = max(a[i:])
suf_max = list(accumulate(reversed(a), max))[::-1]

# 后缀最小
suf_min = list(accumulate(reversed(a), min))[::-1]

配合索引恢复位置（第 i 个前缀最值来自哪个下标）：

# pre_min[i] = min(a[:i+1])，arg[i] = 取到该最小值的最后位置
pre_min, arg = [], []
cur, pos = float('inf'), -1
for i, x in enumerate(a):
    if x < cur:
        cur, pos = x, i
    pre_min.append(cur)
    arg.append(pos)

实战：第3题-待发热度重排 用 pre_min = accumulate(hs, min) 与 suf_max = accumulate(reversed(hs), max)[::-1] 判定序列的不可跨越分割点（前缀最小严格大于后缀最大处切块）。

注意：

• accumulate 返回迭代器，需要 list(...) 物化才能索引
• initial 会让结果长度多 1（n+1 个），适合构造 pre[0] = 0 形式的前缀和数组
• 空 iterable 且不给 initial 时返回空迭代器；给了 initial 至少产出初值一项

全排列

from itertools import permutations, combinations

# 全排列
for perm in permutations(arr):
    print(list(perm))  # [1, 2, 3]

# 组合
for comb in combinations(arr, r):
    pass