用 Python 生成可复现的随机测试数据

随机数据的价值不是“看起来很乱”，而是用很低的编写成本覆盖大量小状态。一个可靠的数据生成器还必须满足题目约束、能够复现失败，并且主动包含纯随机很难碰到的边界结构。

使用独立的随机数生成器

1from random import Random
2
3rng1 = Random(20260715)
4rng2 = Random(20260715)
5
6sequence1 = [rng1.randint(1, 100) for _ in range(5)]
7sequence2 = [rng2.randint(1, 100) for _ in range(5)]
8
9assert sequence1 == sequence2

相同种子和相同调用顺序会产生相同数据。使用 Random(seed) 有两个好处：

不修改模块级的全局随机状态；
每个测试器可以拥有独立、可重放的随机序列。

失败时应记录种子和完整输入，而不是只打印“第 137 组错误”。

生成整数

 1from random import Random
 2
 3rng = Random(1)
 4
 5x = rng.randint(3, 7)
 6y = rng.randrange(3, 8)
 7z = rng.randrange(0, 20, 2)
 8
 9assert 3 <= x <= 7
10assert 3 <= y < 8
11assert 0 <= z < 20 and z % 2 == 0

randint(left, right) 两端都可能取到；
randrange(left, right) 和 range 一样是左闭右开；
randrange(start, stop, step) 可以限制步长。

注意两种区间边界不同，竞赛生成器中这是常见的越界来源。

`choice`、`choices` 与 `sample`

 1from random import Random
 2
 3rng = Random(2)
 4values = [10, 20, 30, 40]
 5
 6one = rng.choice(values)
 7many_with_repetition = rng.choices(values, k=10)
 8many_without_repetition = rng.sample(values, 3)
 9
10assert one in values
11assert len(many_with_repetition) == 10
12assert all(x in values for x in many_with_repetition)
13assert len(many_without_repetition) == 3
14assert len(set(many_without_repetition)) == 3

choice 选择一个元素；
choices 独立选择多次，允许重复；
sample 不放回抽样，结果不重复，要求 k <= len(population)。

带权选择可以给边界值更高概率：

1from random import Random
2
3rng = Random(3)
4values = rng.choices([-1, 0, 1], weights=[1, 5, 1], k=20)
5
6assert len(values) == 20
7assert set(values) <= {-1, 0, 1}

`shuffle` 原地打乱

 1from random import Random
 2
 3rng = Random(4)
 4a = list(range(10))
 5original = a.copy()
 6
 7result = rng.shuffle(a)
 8
 9assert result is None
10assert sorted(a) == original

shuffle 修改原列表并返回 None。需要保留原顺序时先复制：

1from random import Random
2
3rng = Random(5)
4source = [1, 2, 3, 4]
5permutation = source.copy()
6rng.shuffle(permutation)
7
8assert source == [1, 2, 3, 4]
9assert sorted(permutation) == source

数组生成器

把随机逻辑封装成函数，可以单独检查它是否满足约束：

 1from random import Random
 2
 3
 4def random_array(rng, max_n, low, high):
 5    n = rng.randint(0, max_n)
 6    return [rng.randint(low, high) for _ in range(n)]
 7
 8
 9rng = Random(6)
10for _ in range(100):
11    a = random_array(rng, max_n=8, low=-10, high=10)
12    assert 0 <= len(a) <= 8
13    assert all(-10 <= x <= 10 for x in a)

验证程序只需要小规模数据。允许 n = 0、负数和重复值，往往比把范围写成 1..100 更容易发现错误。

不要只生成均匀随机数据

很多 Bug 集中在特殊结构，而均匀随机很难命中。应把手工边界和随机数据合并：

 1def boundary_arrays():
 2    return [
 3        [],
 4        [0],
 5        [1, 1, 1, 1],
 6        [0, 0, 0, 0],
 7        [-5, -2, -9],
 8        [1, 2, 3, 4, 5],
 9        [5, 4, 3, 2, 1],
10        [-(10**9), 10**9],
11    ]
12
13
14cases = boundary_arrays()
15
16assert [] in cases
17assert [1, 1, 1, 1] in cases
18assert [5, 4, 3, 2, 1] in cases

常见边界包括：

空输入和单元素；
全相等、全零、大量重复；
全负数；
已排序和完全逆序；
最小值、最大值及其附近；
答案恰好不存在、恰好唯一或有很多组。

生成合法区间

先生成左端点，再在合法范围内生成右端点：

 1from random import Random
 2
 3
 4def random_nonempty_interval(rng, n):
 5    assert n > 0
 6    left = rng.randrange(n)
 7    right = rng.randrange(left + 1, n + 1)
 8    return left, right
 9
10
11rng = Random(7)
12for _ in range(100):
13    left, right = random_nonempty_interval(rng, 10)
14    assert 0 <= left < right <= 10

直接独立生成两个端点再排序也能工作，但“按约束逐步生成”更容易扩展到复杂结构。

生成随机树

一棵 $n$ 个点的树可以让每个新点连接一个已经存在的点：

 1from random import Random
 2
 3
 4def random_tree(rng, n):
 5    edges = []
 6
 7    for vertex in range(1, n):
 8        parent = rng.randrange(vertex)
 9        edges.append((parent, vertex))
10
11    rng.shuffle(edges)
12    return edges
13
14
15rng = Random(8)
16edges = random_tree(rng, 8)
17
18assert len(edges) == 7
19assert all(0 <= u < 8 and 0 <= v < 8 for u, v in edges)

每个点 vertex > 0 都连接到更早的点，因此图一定连通且没有环。不要随机选 $n-1$ 条边后假设它们自然构成树。

生成简单无向图

先枚举全部可能的无向边，再不放回抽样：

 1from itertools import combinations
 2from random import Random
 3
 4
 5def random_simple_graph(rng, n, m):
 6    possible_edges = list(combinations(range(n), 2))
 7    assert 0 <= m <= len(possible_edges)
 8    return rng.sample(possible_edges, m)
 9
10
11rng = Random(9)
12edges = random_simple_graph(rng, n=6, m=7)
13
14assert len(edges) == 7
15assert len(set(edges)) == 7
16assert all(u < v for u, v in edges)

这种方法只适合验证用的小图，但它天然保证无自环、无重边。

在断言中保存失败信息

 1from random import Random
 2
 3
 4def brute(a):
 5    return sum(a)
 6
 7
 8def candidate(a):
 9    return sum(a)
10
11
12seed = 20260715
13rng = Random(seed)
14
15for case_id in range(100):
16    a = [rng.randint(-10, 10) for _ in range(rng.randint(0, 8))]
17    expected = brute(a)
18    actual = candidate(a)
19
20    assert actual == expected, (
21        f"seed={seed}, case={case_id}, input={a}, "
22        f"expected={expected}, actual={actual}"
23    )

固定种子负责重放整个序列，断言中的完整输入负责直接重放单个失败样例。两者都保留最方便。

完整的暴力函数组织方式见用 Python 快速编写算法暴力验证程序。

参考资料

Python random