Python实现：将百分比差异≤30%的所有值合并为同一分组

我需要计算所有值之间的百分比差异并分组，当前代码仅能输出符合条件的两两组合，但我要把所有**两两百分比差异≤30%**的值合并到同一个分组中。

当前可运行代码 #

from itertools import combinations

def pctDiff(A,B):
    return abs(A-B)*200/(A+B)

def main():
    dict2={}
    dict ={'acct_number':10202,'acct_name':'abc','v1_rev':3000,'v2_rev':4444,'v4_rev':234534,'v5_rev':5665,'v6_rev':66,'v7_rev':66,'v3_rev':66}
    vendors_revenue_list =['v1_rev','v2_rev','v3_rev','v4_rev','v5_rev','v6_rev','v7_rev','v8_rev']
    #prepared list of vendors
    for k in vendors_revenue_list:
        if k in dict.keys():
            dict2.update({k: dict[k]})

    print(dict2)
    #provides all possible combination
    for a, b in combinations(dict2, 2):
        groups = [(a,b) for a,b in combinations(dict2,2) if pctDiff(dict2[a],dict2[b]) <= 30]

    print(groups)

if __name__ == "__main__":
    main()

当前输出 #

[('v2_rev', 'v5_rev'), ('v3_rev', 'v6_rev'), ('v3_rev', 'v7_rev'), ('v6_rev', 'v7_rev')]

期望输出 #

[('v2_rev', 'v5_rev'), ('v3_rev', 'v6_rev','v7_rev')]

解决方案 #

这个问题本质是找图的连通分量：把每个收入项看作节点，两两百分比差异≤30%时，两个节点之间连一条边，最终每个连通分量就是一个合并后的分组。这里用并查集（Union-Find）数据结构来高效实现。

修改后的代码 #

from itertools import combinations

def pctDiff(A, B):
    return abs(A - B) * 200 / (A + B)

class UnionFind:
    def __init__(self, elements):
        self.parent = {elem: elem for elem in elements}
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            self.parent[y_root] = x_root

def main():
    original_dict = {'acct_number':10202,'acct_name':'abc','v1_rev':3000,'v2_rev':4444,'v4_rev':234534,'v5_rev':5665,'v6_rev':66,'v7_rev':66,'v3_rev':66}
    vendors_revenue_list =['v1_rev','v2_rev','v3_rev','v4_rev','v5_rev','v6_rev','v7_rev','v8_rev']
    
    # 筛选存在的收入项
    valid_vendors = {k: original_dict[k] for k in vendors_revenue_list if k in original_dict}
    print("有效收入项:", valid_vendors)
    
    # 初始化并查集
    uf = UnionFind(valid_vendors.keys())
    
    # 遍历所有两两组合，合并符合条件的节点
    for a, b in combinations(valid_vendors.keys(), 2):
        if pctDiff(valid_vendors[a], valid_vendors[b]) <= 30:
            uf.union(a, b)
    
    # 收集连通分量
    groups = {}
    for elem in valid_vendors.keys():
        root = uf.find(elem)
        if root not in groups:
            groups[root] = []
        groups[root].append(elem)
    
    # 转换为期望的元组格式，过滤单个元素的分组
    result = [tuple(sorted(group)) for group in groups.values() if len(group) > 1]
    print("合并后的分组:", result)

if __name__ == "__main__":
    main()

运行结果 #

有效收入项: {'v1_rev': 3000, 'v2_rev': 4444, 'v3_rev': 66, 'v4_rev': 234534, 'v5_rev': 5665, 'v6_rev': 66, 'v7_rev': 66}
合并后的分组: [('v2_rev', 'v5_rev'), ('v3_rev', 'v6_rev', 'v7_rev')]

代码说明 #

1. 并查集类：实现find（查找根节点）和union（合并节点）方法，高效管理节点的连通关系。
2. 筛选有效项：只保留原始字典中存在的收入项，避免无效键报错。
3. 合并节点：遍历所有两两组合，将百分比差异符合条件的节点合并到同一连通分量。
4. 收集分组：根据根节点归类同一连通分量的元素，转换为元组格式输出，同时过滤掉单个元素的分组（若需要保留可去掉长度判断）。

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