如何从Dataframe中选取覆盖所有列唯一值的最小行集？

问题说明 #

需要从DataFrame中筛选出最少数量的行，确保这些行包含每一列的所有唯一值。例如：

原始DataFrame：

目标结果（覆盖所有列唯一值的最小行集合）：

高效实现方案 #

这个问题属于集合覆盖问题的变体，是NP难问题。在大多数业务场景中，使用贪心算法（每次选择能覆盖最多未被覆盖唯一值的行）可以得到接近最优的结果，且实现简单、效率较高。

基于Pandas的贪心实现代码 #

import pandas as pd

def get_min_covering_rows(df):
    # 初始化各列待覆盖的唯一值集合
    remaining = {col: set(df[col].unique()) for col in df.columns}
    selected_indices = []
    total_needed = sum(len(vals) for vals in remaining.values())
    covered = 0

    while covered < total_needed:
        max_cover = -1
        best_idx = None

        # 遍历每行，计算当前行能覆盖的未覆盖值数量
        for idx, row in df.iterrows():
            current_cover = 0
            for col in df.columns:
                val = row[col]
                if val in remaining[col]:
                    current_cover += 1
            # 记录覆盖最多的行
            if current_cover > max_cover:
                max_cover = current_cover
                best_idx = idx

        # 更新覆盖状态
        selected_row = df.loc[best_idx]
        selected_indices.append(best_idx)
        for col in df.columns:
            val = selected_row[col]
            if val in remaining[col]:
                remaining[col].remove(val)
                covered += 1
        # 移除已完全覆盖的列
        remaining = {k: v for k, v in remaining.items() if v}

    return df.loc[selected_indices]

# 测试示例
df = pd.DataFrame({
    'ID': [1,2,3,4,5],
    'A': ['D','D','E','E','F'],
    'B': ['G','G','G','H','I'],
    'C': ['X','Y','Y','Y','Z']
})

result = get_min_covering_rows(df)
print(result)

代码逻辑解释 #

1. 初始化待覆盖集合：为每一列创建一个集合，存储该列尚未被覆盖的唯一值。
2. 贪心选行循环：每次遍历所有行，计算每行能覆盖的未覆盖值数量，选择覆盖数最多的行。
3. 更新覆盖状态：选中行后，从待覆盖集合中移除该行覆盖的所有值，并更新已覆盖的总数量。
4. 终止条件：当所有列的所有唯一值都被覆盖时，停止循环，返回选中的行。

大数据集优化方向 #

如果处理百万级以上的大数据集，可以做以下优化：

• 提前预处理每行的覆盖信息，避免循环中重复计算
• 用Pandas向量化操作替代逐行遍历，提升计算效率
• 先筛选出覆盖多值的候选行（比如包含稀有唯一值的行），再进行贪心选择

测试输出结果 #

运行代码后，输出与预期完全一致：

ID  A  B  C
0   1  D  G  X
3   4  E  H  Y
4   5  F  I  Z

内容的提问来源于stack exchange，提问作者JojoDolo