Python中按元组指定键排序时，如何获取所有无tie-breaker的合法排序结果？

给定元组列表：

my_list = [(1, 100), (2, 100), (1, 101)]

使用常规排序sorted(my_list, key=lambda x: x[1])会得到其中一种合法排序结果，但当存在键值相同的元素时，我们需要获取所有符合排序规则的排列（相同键值的元素顺序可任意，不同键值的元素必须保持排序后的相对顺序），预期输出：

[[(1, 100), (2, 100), (1, 101)], [(2, 100), (1, 100), (1, 101)]]

高效实现思路 #

直接生成全排列再筛选的效率极低，尤其是当列表规模较大时。更优的方式是：

1. 先按排序键对原列表排序，确保不同键值的元素组顺序正确，同时将相同键值的元素集中在一起。
2. 按键值分组，得到每个键对应的元素列表。
3. 对每个相同键值的元素组生成所有可能的排列（因为组内元素顺序不影响排序合法性）。
4. 通过笛卡尔积将各组的排列组合起来，再拼接成完整的合法排序列表。

代码实现 #

import itertools

def get_all_sorts(my_list, key_func=lambda x: x[1]):
    # 先按指定键排序，确保不同键的组顺序正确，同时相同键的元素聚集
    sorted_by_key = sorted(my_list, key=key_func)
    # 按键分组，得到同键元素的分组列表
    groups = []
    current_key = None
    current_group = []
    for item in sorted_by_key:
        key = key_func(item)
        if key != current_key:
            if current_group:
                groups.append(current_group)
            current_key = key
            current_group = [item]
        else:
            current_group.append(item)
    if current_group:
        groups.append(current_group)
    
    # 对每个组生成所有排列
    group_permutations = [itertools.permutations(group) for group in groups]
    # 组合各组排列，拼接成完整的合法排序列表
    all_valid_sorts = []
    for perm_combination in itertools.product(*group_permutations):
        valid_sort = []
        for perm in perm_combination:
            valid_sort.extend(perm)
        all_valid_sorts.append(valid_sort)
    
    return all_valid_sorts

# 测试示例
my_list = [(1, 100), (2, 100), (1, 101)]
print(get_all_sorts(my_list))

代码说明 #

• 分组阶段：手动遍历排序后的列表完成分组，逻辑直观清晰（也可以用itertools.groupby替代，前提是输入已排序）。
• 排列生成：仅对相同键值的小分组生成排列，避免了对整个列表生成全排列。例如列表有10个元素、其中2个键值相同时，全排列需生成3628800种，而此方法仅需2种组合，效率差距极大。
• 笛卡尔积组合：保证不同键值的组顺序与排序后的顺序一致，同时覆盖所有组内元素的合法排列。

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