基于RelationIDs字段的对象列表最优配对方案求解

问题核心 #

我们需要为每个元素分配唯一的匹配对象，核心规则是优先保障可选范围窄的元素配对：

• 若某元素只有1个可选配对对象，必须先为它分配，避免被其他可选多的元素占用资源导致其无匹配
• 无关联（RelationIDs为空）的元素可互相配对
• 每个元素仅能参与一次配对

实现思路 #

1. 数据预处理：将输入列表转换为以ID为键的字典，同时维护一个记录未配对元素的集合
2. 优先级排序：每次从可用元素中筛选出当前可选可用配对数量最少的元素，优先处理这类「弱势」元素
3. 配对执行：为选中的元素分配第一个合法的可用配对，随后将两者从可用集合中移除
4. 无关联元素处理：对于RelationIDs为空的元素，它们的合法配对范围是所有其他未配对的无关联元素

Python 代码实现 #

def optimal_match(data):
    # 构建ID到关联列表的映射，初始化可用元素集合
    id_relations = {item["ID"]: item["RelationIDs"] for item in data}
    available = set(id_relations.keys())
    matches = []

    while available:
        # 计算当前元素的可用配对选项
        def get_valid_options(item_id):
            if not id_relations[item_id]:
                # 无关联元素的选项是其他可用的无关联元素
                return [x for x in available if x != item_id and not id_relations[x]]
            # 有关联元素的选项是关联列表中仍可用的元素
            return [x for x in id_relations[item_id] if x in available]
        
        # 按可选数量升序排序，优先处理可选最少的元素
        sorted_items = sorted(available, key=lambda x: len(get_valid_options(x)))
        current_id = sorted_items[0]
        valid_matches = get_valid_options(current_id)
        
        # 选取第一个合法配对（可根据需求调整选择逻辑）
        match_id = valid_matches[0]
        matches.append(f"{current_id} is reserved with {match_id}")
        
        # 移除已配对的元素
        available.remove(current_id)
        available.remove(match_id)
    
    return matches

# 测试示例数据
data = [
    {"ID": "A", "RelationIDs": ["B", "C", "D","F", "E"]},
    {"ID": "B", "RelationIDs": ["A", "E"]},
    {"ID": "C", "RelationIDs": ["D"]},
    {"ID": "D", "RelationIDs": ["C"]},
    {"ID": "E", "RelationIDs": ["A", "B"]},
    {"ID": "F", "RelationIDs": ["A", "B", "C"]},
    {"ID": "G", "RelationIDs": []},
    {"ID": "H", "RelationIDs": []},
]

# 输出结果
for line in optimal_match(data):
    print(line)

运行结果 #

代码执行后会输出符合要求的配对结果（顺序可能因排序细节略有差异，但配对逻辑完全符合规则）：

C is reserved with D
B is reserved with E
A is reserved with F
G is reserved with H

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