Python如何按指定规则重排二元整数元组列表

问题说明 #

现有存储二元整数元组的输入列表：

input_list = [(1, 2), (2, 2), (3, 2), (5, 3), (7, 3), (4, 4)]

需按以下规则完成元组重排：

• 轮询选取规则：每一轮选取时，按元组第二个元素升序的顺序依次选取，样例选取序列的第二个元素依次为2、3、4、2、3、2
• 同值选取规则：同一轮中，相同第二个元素的待选元组里，优先选取第一个元素值最小的元组，已选取的元组不参与后续选取。
  目标输出结果：

output_list = [(1, 2), (5, 3), (4, 4), (2, 2), (7, 3), (3, 2)]

实现思路 #

1. 先将所有待选元组按第二个元素的值分组，每个分组内部按元组第一个元素升序排序，转为支持头部快速弹出的队列结构，保证每次取同组元素时都能拿到当前剩余的最小首元素值的元组
2. 提前将分组的key（即元组第二个元素）按升序排列，作为每一轮轮询的固定遍历顺序
3. 循环执行轮询逻辑：按升序遍历所有分组key，若对应分组还有剩余未选元素，就弹出队首元素加入结果列表；若分组已空则直接跳过
4. 当结果列表长度和输入列表长度一致时，停止循环，返回结果即可

代码实现（Python） #

from collections import defaultdict, deque

def tuple_rearrange(input_arr):
    # 按第二个元素分组
    group_map = defaultdict(list)
    for t in input_arr:
        group_map[t[1]].append(t)
    # 确定轮询的key顺序：按第二个元素升序
    poll_order = sorted(group_map.keys())
    # 每个分组按第一个元素升序排序后转双端队列
    for k in group_map:
        group_map[k].sort(key=lambda x: x[0])
        group_map[k] = deque(group_map[k])
    
    res = []
    total = len(input_arr)
    while len(res) < total:
        for k in poll_order:
            if group_map[k]:
                res.append(group_map[k].popleft())
    return res

# 样例测试
if __name__ == "__main__":
    input_list = [(1, 2), (2, 2), (3, 2), (5, 3), (7, 3), (4, 4)]
    print(tuple_rearrange(input_list))
    # 输出结果：[(1, 2), (5, 3), (4, 4), (2, 2), (7, 3), (3, 2)]，与目标完全匹配

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