本文介绍一种基于图论最大独立集的高效方法，解决在保持两列值全部唯一前提下、删除最少行数的问题，避免贪心去重导致的次优解。
本文介绍一种基于图论最大独立集的高效方法，解决在保持两列值全部唯一前提下、删除最少行数的问题，避免贪心去重导致的次优解。
在处理结构化数据时，常需满足“每列元素互不重复”的约束（例如构建一一映射关系、分配唯一资源对等场景）。直观地对每列分别调用 drop_duplicates() 会因顺序依赖和局部最优导致过度删减——如示例中原始 6 行被删至 3 行，而实际存在保留 4 行的合法解（如 [row0, row1, row4, row5]）。
该问题本质是组合优化问题：目标是选出最大数量的行，使得任意两行在 column1 上不重复 且 在 column2 上也不重复。换言之，所选行集合中，column1 值互异、column2 值也互异。这等价于在冲突图（Conflict Graph） 上求最大独立集（Maximum Independent Set, MIS）：
- 每一行对应图中的一个顶点；
- 若两行在 column1 或 column2 上存在相同值，则二者之间连一条边（表示冲突，不可同时保留）；
- 独立集即为无边相连的顶点子集 → 对应无冲突的行子集；
- 最大独立集 → 保留行数最多 → 删除行数最少。
虽然精确求解 MIS 是 NP-hard 问题，但 networkx 提供了高效的近似算法 maximum_independent_set()（基于补图的最大团启发式），在中小规模数据（数千行内）上表现稳定且结果质量高。
以下是完整实现代码：
import pandas as pd
import networkx as nx
from networkx.algorithms.approximation.clique import maximum_independent_set
from itertools import combinations
# 示例数据
df = pd.DataFrame({
'column1': [1, 2, 3, 1, 3, 4],
'column2': [5, 6, 7, 8, 9, 7]
})
# 构建冲突图
G = nx.Graph()
G.add_nodes_from(range(len(df))) # 节点：行索引 0,1,...,n-1
# 遍历所有行对，若 column1 相同 或 column2 相同，则添加边
rows = list(df.iterrows())
for (i, row_i), (j, row_j) in combinations(rows, 2):
if row_i['column1'] == row_j['column1'] or row_i['column2'] == row_j['column2']:
G.add_edge(i, j)
# 求近似最大独立集（返回节点索引列表）
mis_indices = maximum_independent_set(G)
# 按索引升序选取对应行，保持原始顺序语义
result_df = df.iloc[sorted(mis_indices)].reset_index(drop=True)
print("Optimal subset (min rows removed):")
print(result_df)
输出：
Optimal subset (min rows removed): column1 column2 0 1 5 1 2 6 2 3 9 3 4 7
✅ 此结果保留 4 行（仅删 2 行），满足 column1=[1,2,3,4] 全唯一、column2=[5,6,9,7] 全唯一，达到理论最小删除量。
注意事项：
- 该方法时间复杂度约为 O(n²)，适用于 n ≤ 5000 的典型业务数据；若数据量极大（>10⁴ 行），建议先采样分析或引入启发式预剪枝（如优先保留高频值稀疏的行）；
- maximum_independent_set 返回的是近似解，但实践中对多数稀疏冲突图精度极高；如需精确解，可改用 nx.max_weight_clique(G_complement)（需构造补图并赋权），但计算开销显著增加；
- 若后续需扩展至多列（如三列均需唯一），仍可沿用图模型：只要任意一列值冲突即连边，MIS 含义不变。
综上，将数据清洗问题建模为图论独立集问题，不仅语义清晰、逻辑严谨，还能借助成熟图算法库获得高质量、可解释的最优（或近优）解，远优于启发式顺序去重。
