Python如何根据指定模式字典对列表进行自定义排序

实现思路 #

• 首元素固定为输入列表的第一个元素，无需调整
• 每次取已排序部分的最后一个元素，查询模式字典中该元素允许的后续元素列表
• 从剩余未选择的元素中，匹配到第一个出现在允许后续列表中的元素，加入已排序部分
• 重复上述步骤直到所有元素都被排序

完整实现代码 #

def sort_by_pattern(input_list, pattern):
    if len(input_list) <= 1:
        return input_list.copy()
    # 初始化已排序、待选元素
    sorted_list = [input_list[0]]
    remaining = input_list[1:].copy()
    
    while remaining:
        current_last = sorted_list[-1]
        # 遍历当前元素允许的后续元素，找第一个在待选列表里的
        for allowed_next in pattern[current_last]:
            if allowed_next in remaining:
                sorted_list.append(allowed_next)
                remaining.remove(allowed_next)
                break
    return sorted_list

# 测试用例1
pattern = {'West'   : ['North','Central'],
           'North'  : ['West','Alpha','Bravo','Central'],
           'Alpha'  : ['Bravo','North'],
           'Bravo'  : ['North','Alpha','Central','Middle'],
           'Central': ['West','North','Bravo','Middle'],
           'Middle' : ['Bravo','Central','South'],
           'South'  : ['Middle'] 
          }
listA = ['West','North','Middle','Bravo']
resultA = sort_by_pattern(listA, pattern)
print(resultA) # 输出 ['West', 'North', 'Bravo', 'Middle']

# 测试用例2
listB = ['South','Central','West','Middle']
resultB = sort_by_pattern(listB, pattern)
print(resultB) # 输出 ['South', 'Middle', 'Central', 'West']

注意事项 #

• 该实现默认给定的输入列表一定存在符合规则的排序结果，若输入存在无合法后续的场景，可以根据需求额外添加异常处理逻辑
• 匹配后续元素时优先按照模式字典中对应列表的顺序选择，和示例规则完全对齐

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