Python字典遍历：实现投票规则找出最终胜出备选方案集

问题背景 #

投票规则分轮次进行：每一轮移除代理排名首位出现频率最低的备选方案，重复此过程。当最后一组备选方案被移除（一个或多个）时，该组即为胜出者集合，需返回这个最终集合。

偏好配置文件是一个字典，键为代理，值为该代理的备选方案偏好排名列表（1代表最偏好）。示例配置如下：

preferences = {
 1: [4, 2, 1, 3],
 2: [4, 3, 1, 2],
 3: [2, 3, 1, 2],
 4: [1, 3, 4, 2],
 5: [2, 3, 4, 1],
 6: [2, 1, 3, 4]
}

原代码能正确计算每一轮的首位频率，但无法识别最终胜出集合。示例中，原代码最终输出{2}，而期望输出是{4, 2}（当剩余元素频率相同时，这组就是最终胜出集合）。

原代码如下：

def votingRule(preferences):
    dictionary = preferences.copy()
    removed_values = set()
    while dictionary:
        values = set()
        for vals in dictionary.values():
            values.update(vals) 
        
        frequencies = {value: 0 for value in values}
        for values in dictionary.values():
            try:
                if values[0] in frequencies:
                    frequencies[values[0]] += 1 
            except IndexError:
                pass
        print("1st Freqs",frequencies) # this stage returns a correct count of each element

        if not frequencies:
            return set()
        min_frequency = min(frequencies.values())
           
        current_removed_values = set()
        for value in frequencies:
            for ele in dictionary:
                if frequencies[value] == min_frequency:
                    for key in dictionary:
                        if value in dictionary[key]:
                            dictionary[key].remove(value)
                            current_removed_values.add(value)
                break
            else:
                dictionary = {}                            
        removed_values = current_removed_values      
    return removed_values

代码问题分析 #

1. 未处理剩余元素频率全相等的情况：当所有剩余备选方案的首位频率相同时，这组就是最终胜出集合，应该直接返回，而非继续移除。
2. 移除逻辑混乱：嵌套循环导致只处理了第一个频率最低的元素，没有收集所有频率最低的元素一起移除。
3. 字典拷贝问题：原代码的dictionary = preferences.copy()是浅拷贝，修改列表元素会影响原数据（示例中未触发，但存在隐患）。

修正后的代码 #

def votingRule(preferences):
    # 深拷贝，避免修改原字典的列表
    preferences_copy = {k: v.copy() for k, v in preferences.items()}
    remaining_candidates = set()
    for vals in preferences_copy.values():
        remaining_candidates.update(vals)
    
    while remaining_candidates:
        # 统计当前所有代理首位候选的频率
        freq = {}
        for vals in preferences_copy.values():
            if vals:  # 确保列表非空
                top = vals[0]
                freq[top] = freq.get(top, 0) + 1
        
        # 处理所有候选都被移除的极端情况
        if not freq:
            return set()
        
        # 检查是否所有剩余候选的频率相同
        all_freqs = list(freq.values())
        if all(f == all_freqs[0] for f in all_freqs):
            return remaining_candidates
        
        # 找到最低频率，收集所有要移除的候选
        min_freq = min(freq.values())
        to_remove = {c for c, count in freq.items() if count == min_freq}
        
        # 从所有代理的偏好列表中移除这些候选
        for vals in preferences_copy.values():
            for c in to_remove:
                if c in vals:
                    vals.remove(c)
        
        # 更新剩余候选集合
        remaining_candidates -= to_remove
    
    return set()

关键改动说明 #

• 深拷贝偏好字典：避免修改原数据，保证数据独立性。
• 新增剩余候选集合：直接跟踪剩余候选，无需每次遍历所有列表收集。
• 频率全相等判断：当所有剩余候选的首位频率一致时，直接返回该集合，终止循环。
• 批量移除候选：一次性收集所有频率最低的候选，统一移除，避免遗漏。

测试示例代码，输入给定的preferences，将返回{2, 4}，符合预期。

更高效的实现方式 #

可以用更简洁的逻辑，结合collections模块简化频率统计，同时优化循环逻辑：

from collections import defaultdict

def votingRule(preferences):
    # 深拷贝
    prefs = {k: v.copy() for k, v in preferences.items()}
    # 初始化所有候选
    candidates = set()
    for lst in prefs.values():
        candidates.update(lst)
    
    while candidates:
        # 统计首位候选频率
        top_counts = defaultdict(int)
        for lst in prefs.values():
            if lst:
                top_counts[lst[0]] += 1
        
        if not top_counts:
            return set()
        
        # 判断是否所有频率相同
        counts = list(top_counts.values())
        if len(set(counts)) == 1:
            return candidates
        
        # 找到最低频率对应的候选
        min_count = min(counts)
        to_remove = {c for c, cnt in top_counts.items() if cnt == min_count}
        
        # 移除候选
        for lst in prefs.values():
            for c in to_remove:
                if c in lst:
                    lst.remove(c)
        
        candidates -= to_remove
    
    return set()

优化点 #

• 使用collections.defaultdict简化频率统计代码。
• 用len(set(counts)) == 1快速判断所有频率是否一致，逻辑更简洁。
• 整体代码结构更清晰，可读性更强。

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