因子聚簇计数:阈值化相关性图的连通分量数
Factor Cluster Count: Connected Components on a Thresholded Correlation Graph
开始编码实现 solution(corr: list[list[float]], tau: float) -> int。给定边长 N 的对称相关性矩阵 corr(满足 corr[i][i] = 1.0 与 corr[i][j] = corr[j][i])以及阈值 tau 落在开区间 (0.0, 1.0) 中:在 N 个下标 0..N-1 上构建无向图,当 i != j 且 abs(corr[i][j]) >= tau 时在 i, j 之间连一条边,返回该图的连通分量数。
例
solution([[1.0, 0.9, 0.1], [0.9, 1.0, 0.2], [0.1, 0.2, 1.0]], 0.5) 返回 2。下标 0 与 1 由 |0.9| >= 0.5 相连;下标 2 与两者都不连,因此分量为 {0, 1} 与 {2}。再看一个负相关聚簇判定:solution([[1.0, -0.6], [-0.6, 1.0]], 0.5) 返回 1——负相关 -0.6 的绝对值 0.6 >= 0.5,两个名字属于同一聚簇。最后 solution([], 0.3) 返回 0(空 universe),solution([[1.0]], 0.3) 返回 1(单个孤立名字自身构成一个平凡聚簇)。
预期解法在严格上三角上一遍扫边,把连接送进带路径压缩与按秩合并的并查集,并在每次成功合并时把分量计数器减一;用基于邻接表的迭代式 BFS 或 DFS 等价。Floyd-Warshall 式的传递闭包扫描是 O(N^3),在 N 接近上限时会超时;要意识到只需要连通分量这一划分,并不需要完整闭包矩阵。
需要明确的契约细节:阈值采用闭包含(>=,不是严格 >);负相关按绝对值参与判定(在 tau = 0.5 下 -0.5 与 +0.5 耦合等同);对角线 corr[i][i] 被排除在边集之外(这种自环并不改变连通性,但会让每个节点先自连一遍,污染下游图统计——契约把它划在外)。空矩阵 (N == 0) 与单元素 (N == 1) 在 tau 边界检查之前短路返回(无论阈值取值,答案 0 与 1 都是平凡定义良好的);当 N >= 2 时阈值真正决定连边,因此先校验 tau。若 tau 落在 (0, 1) 之外(包括端点 0.0 与 1.0 本身),或 corr 在 1e-9 容差之外不对称,请抛出 ValueError 而不是返回半成品计数。
实现细节由 stubs/stub.py 提供。
实践背景
层次化风险平价、因子分桶、相关性聚簇诊断,这几件事在可交易 universe 上都从同一个原语出发:取 N 个名字之间的两两相关性矩阵(通常由滚动窗口的收益率估出),先按阈值砍掉噪声级别的耦合,再问这一 universe 在独立风险维度上分成几块。连通分量数是最便宜的标量摘要——它告诉交易台:universe 是一整个宏观押注、几个行业捆扎、还是接近正交的篮子。风险线会每晚换几个候选 tau 跑这条流水线,把分量数随阈值松紧而变化的曲线(树状图谱)画出来;组合构建侧直接拿这个划分给资本分配,因此分量数若错一个,下游的桶级权重就会带着误差偷偷传播。绝对值规则是有意为之:从对冲视角看,-0.8 的相关性与 +0.8 一样会撞上同一根风险轴;闭区间 >= 与策略文档里写阈值的方式一致("对 |rho| 不低于 0.5 的名字做聚簇")。
约束条件
- 0 <= N <= 400,其中 N 是 corr 矩阵的边长
- corr 是 N x N 的实数方阵,满足 corr[i][i] = 1.0 与 corr[i][j] = corr[j][i](对称性在 1e-9 容差内校验,超出容差的硬不对称会抛 ValueError)
- tau 必须满足 0.0 < tau < 1.0;落在该开区间之外(包括 0.0 与 1.0)的取值会抛 ValueError
- i != j 且 abs(corr[i][j]) >= tau 时连边(阈值闭包含,对负相关同样有效)
- N == 0 时返回 0、N == 1 时返回 1 在 tau 校验之前短路;N >= 2 时输出为非负整数,使用精确比对
样例
Case 1 · statement-example: three nodes, two clusters
输入: [[[1,0.9,0.1],[0.9,1,0.2],[0.1,0.2,1]],0.5]
期望: 2
下标 0 与 1 由 |0.9| >= 0.5 连通;下标 2 不与任何节点连通,分量数为 2。
Case 2 · visible: negative correlation forms one cluster
输入: [[[1,-0.6],[-0.6,1]],0.5]
期望: 1
负相关 -0.6 的绝对值 0.6 >= 0.5,两个名字属于同一聚簇,分量数为 1。
Case 3 · visible: empty matrix returns 0
输入: [[],0.3]
期望: 0
空 universe,无任何节点,分量数为 0。
Case 4 · visible: single node returns 1
输入: [[[1]],0.3]
期望: 1
单个孤立名字本身构成一个平凡聚簇,分量数为 1。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: three nodes, two clusters
输入: [[[1,0.9,0.1],[0.9,1,0.2],[0.1,0.2,1]],0.5]
期望: 2
下标 0 与 1 由 |0.9| >= 0.5 连通;下标 2 不与任何节点连通,分量数为 2。
Case 2 · visible: negative correlation forms one cluster
输入: [[[1,-0.6],[-0.6,1]],0.5]
期望: 1
负相关 -0.6 的绝对值 0.6 >= 0.5,两个名字属于同一聚簇,分量数为 1。
Case 3 · visible: empty matrix returns 0
输入: [[],0.3]
期望: 0
空 universe,无任何节点,分量数为 0。
Case 4 · visible: single node returns 1
输入: [[[1]],0.3]
期望: 1
单个孤立名字本身构成一个平凡聚簇,分量数为 1。