如何使用Python列表依据标准列表对输入列表进行分区与重排？

标准列表定义 #

我们有四个预定义的标准列表：

v1 = ['Elisa', 'Liza', 'Izabela', 'Elisabeth', 'Elizabeth', 'Lisa', 'Lizzy', 'Isabella', 'Isabelle', 'Isabela', 'Liz']
v2 = ['Abbey', 'Abbie', 'Abigail', 'Abby', 'Gail']
v3 = ['Jonathan', 'Jon', 'John', 'Jonny', 'Johnny', 'Nathan']
v4 = ['Alejandra','Alexandra','Alexis','Alya','Alexa','Lexi','Allie','Ally']

输入输出规则 #

给定输入列表a，满足每个标准列表在a中恰好有一个对应元素。我们需要：

1. 以这些来自标准列表的元素为锚点，将a分割为四个连续分区
2. 按照「v1对应分区 → v2对应分区 → v3对应分区 → v4对应分区」的顺序重新拼接分区，得到目标列表

示例展示 #

示例1 #

输入列表：

a = ['Jonathan', 'Jim', 'Jennifer', 'Alya', 'Renee', 'Natasha', 'Phil', 'Lisa', 'Joe', 'Ana', 'Paul', 'Gail', 'Roderick', 'Patricia']

预期输出：

a_out = ['Lisa', 'Joe', 'Ana', 'Paul', 'Gail', 'Roderick', 'Patricia', 'Jonathan', 'Jim', 'Jennifer', 'Alya', 'Renee', 'Natasha', 'Phil']

示例2 #

输入列表：

a = ['Abby', 'Robin', 'Natasha', 'Frank', 'Ana', 'Jennifer', 'Elizabeth', 'Tanya', 'Jim', 'Will', 'Rob', 'Joe', 'Alexa', 'Roger', 'Adam', 'Paul', 'James', 'Kara', 'John', 'Jeff', 'Rick', 'Steve']

预期输出：

a_out = ['Elizabeth', 'Tanya', 'Jim', 'Will', 'Rob', 'Joe', 'Abby', 'Robin', 'Natasha', 'Frank', 'Ana', 'Jennifer', 'John', 'Jeff', 'Rick', 'Steve', 'Alexa', 'Roger', 'Adam', 'Paul', 'James', 'Kara']

实现思路 #

1. 将标准列表转换为集合，提升元素归属判断的效率
2. 遍历输入列表，找到每个标准列表对应的锚点元素及其索引
3. 根据锚点索引的位置，将列表分割为对应分区
4. 按指定顺序拼接分区得到结果

Python代码实现 #

# 定义标准列表及对应的集合
v1 = ['Elisa', 'Liza', 'Izabela', 'Elisabeth', 'Elizabeth', 'Lisa', 'Lizzy', 'Isabella', 'Isabelle', 'Isabela', 'Liz']
v2 = ['Abbey', 'Abbie', 'Abigail', 'Abby', 'Gail']
v3 = ['Jonathan', 'Jon', 'John', 'Jonny', 'Johnny', 'Nathan']
v4 = ['Alejandra','Alexandra','Alexis','Alya','Alexa','Lexi','Allie','Ally']

set_v1 = set(v1)
set_v2 = set(v2)
set_v3 = set(v3)
set_v4 = set(v4)

def reorder_list(a):
    # 记录每个锚点的索引
    anchors = {}
    for idx, name in enumerate(a):
        if name in set_v1:
            anchors['v1'] = idx
        elif name in set_v2:
            anchors['v2'] = idx
        elif name in set_v3:
            anchors['v3'] = idx
        elif name in set_v4:
            anchors['v4'] = idx
    
    # 提取锚点索引并排序，用于分割列表
    sorted_indices = sorted(anchors.values())
    parts = []
    prev = 0
    for idx in sorted_indices:
        parts.append(a[prev:idx+1])
        prev = idx + 1
    
    # 建立锚点索引到分区的映射
    idx_part_map = {anchors[key]: part for key, part in zip(['v1','v2','v3','v4'], parts)}
    
    # 按指定顺序拼接分区
    return idx_part_map[anchors['v1']] + idx_part_map[anchors['v2']] + idx_part_map[anchors['v3']] + idx_part_map[anchors['v4']]

# 测试示例1
a1 = ['Jonathan', 'Jim', 'Jennifer', 'Alya', 'Renee', 'Natasha', 'Phil', 'Lisa', 'Joe', 'Ana', 'Paul', 'Gail', 'Roderick', 'Patricia']
print(reorder_list(a1))

# 测试示例2
a2 = ['Abby', 'Robin', 'Natasha', 'Frank', 'Ana', 'Jennifer', 'Elizabeth', 'Tanya', 'Jim', 'Will', 'Rob', 'Joe', 'Alexa', 'Roger', 'Adam', 'Paul', 'James', 'Kara', 'John', 'Jeff', 'Rick', 'Steve']
print(reorder_list(a2))

代码说明 #

• 把标准列表转为集合，利用集合O(1)的成员查询效率，替代列表O(n)的查询
• 遍历输入列表时，逐个标记每个标准组对应的锚点位置
• 通过排序锚点索引，将原列表分割为四个连续分区，每个分区包含一个锚点及该锚点到下一个锚点前的所有元素
• 建立锚点与分区的映射后，按v1→v2→v3→v4的顺序拼接分区，得到最终结果

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