如何非索引比对两个列表并标记违反排序规则的元素

问题背景 #

• 存在两个列表：
  • ordered_list：固定顺序的西班牙语词汇列表，排序不可修改，允许重复元素
  • unordered_list：包含与ordered_list完全相同的元素，但顺序不同，且两个列表长度一致、首元素相同、重复元素不可移除
• 需求：生成result_list，保留unordered_list原有顺序，仅给违反ordered_list排序规则的元素添加$标记（重复元素中仅提前出现的违规实例需要标记，后续符合顺序的无需标记）

示例列表：

ordered_list = ['a', 'aba', 'abaá', 'ababillarse', 'ababol', 'abacá', 'abacal', 'abacalero', 'abacería', 'abacero', 'abacial', 'ábaco', 'abacora', 'abacorar', 'abad', 'abad', 'abada', 'abadejo', 'abadengo', 'abadernar', 'abadesa', 'abadí', 'abadía', 'abadía', 'abadiado', 'abadiato', 'abajadero', 'abajamiento', 'ábax', 'aceite', 'aceite', 'ancianos', 'ár', 'arquitrabe', 'arquitrabe']
unordered_list = ['a', 'ancianos', 'aba', 'abaá', 'ababillarse', 'ababol', 'ár', 'abacá', 'abacal', 'abacalero', 'abacería', 'aceite', 'abacero', 'abacial', 'abadía', 'ábaco', 'ábax', 'arquitrabe', 'abacora', 'abacorar', 'abad', 'abad', 'abada', 'abadejo', 'abadengo', 'abadernar', 'abadesa', 'abadí', 'abadía', 'abadiado', 'abadiato', 'abajadero', 'abajamiento', 'aceite', 'arquitrabe']

期望输出：

result_list = ['a', '$ancianos', 'aba', 'abaá', 'ababillarse', 'ababol', '$ár', 'abacá', 'abacal', 'abacalero', 'abacería', '$aceite', 'abacero', 'abacial', '$abadía', 'ábaco', '$ábax', '$arquitrabe', 'abacora', 'abacorar', 'abad', 'abad', 'abada', 'abadejo', 'abadengo', 'abadernar', 'abadesa', 'abadí', 'abadía', 'abadiado', 'abadiato', 'abajadero', 'abajamiento', 'aceite', 'arquitrabe']

错误尝试及问题 #

以下代码错误地标记了大部分元素：

def get_correct_order_with_marker(ordered_list , unordered_list , marker='$'):
    # 建立词汇到有序列表索引的映射
    order_dict = {word: index for index, word in enumerate(ordered_list)}

    # 按有序列表规则排序无序列表
    sorted_unordered_list = sorted(unordered_list, key=lambda x: order_dict[x])

    # 标记位置变动的元素
    marked_unordered_list = [f"{marker}{word}" if word != sorted_unordered_list[idx] else word for idx, word in enumerate(unordered_list)]

    return marked_unordered_list

# 示例调用
ordered_list  = ['a', 'aba', 'abaá', 'ababillarse', 'ababol', 'abacá', 'abacal', 'abacalero', 'abacería', 'abacero', 'abacial', 'ábaco', 'abacora', 'abacorar', 'abad', 'abad', 'abada', 'abadejo', 'abadengo', 'abadernar', 'abadesa', 'abadí', 'abadía', 'abadía', 'abadiado', 'abadiato', 'abajadero', 'abajamiento', 'ábax', 'aceite', 'aceite', 'ancianos', 'ár', 'arquitrabe', 'arquitrabe']

unordered_list = ['a', 'ancianos', 'aba', 'abaá', 'ababillarse', 'ababol', 'ár', 'abacá', 'abacal', 'abacalero', 'abacería', 'aceite', 'abacero', 'abacial', 'abadía', 'ábaco', 'ábax', 'arquitrabe', 'abacora', 'abacorar', 'abad', 'abad', 'abada', 'abadejo', 'abadengo', 'abadernar', 'abadesa', 'abadí', 'abadía', 'abadiado', 'abadiato', 'abajadero', 'abajamiento', 'aceite', 'arquitrabe']

result_list  = get_correct_order_with_marker(ordered_list , unordered_list)
print(result_list )

错误输出：

['a', '$ancianos', '$aba', '$abaá', '$ababillarse', '$ababol', '$ár', '$abacá', '$abacal', '$abacalero', '$abacería', '$aceite', '$abacero', '$abacial', '$abadía', '$ábaco', '$ábax', 'arquitrabe', '$abacora', '$abacorar', '$abad', '$abad', '$abada', '$abadejo', '$abadengo', '$abadernar', '$abadesa', '$abadí', '$abadía', '$abadiado', '$abadiato', '$abajadero', '$abajamiento', '$aceite', 'arquitrabe']

问题根源：

1. 字典映射会覆盖重复元素的索引，导致排序逻辑错误
2. 直接对比排序后的列表与原无序列表的位置，无法处理重复元素的顺序匹配需求

正确实现方案 #

核心思路：跟踪ordered_list中每个元素的使用进度，遍历unordered_list时，检查当前元素是否是ordered_list中当前进度之后的下一个可出现元素（考虑重复），不符合则标记，符合则推进进度。

代码实现：

def get_correct_order_with_marker(ordered_list, unordered_list, marker='$'):
    from collections import defaultdict
    # 记录每个单词在ordered_list中的所有出现位置
    pos_map = defaultdict(list)
    for idx, word in enumerate(ordered_list):
        pos_map[word].append(idx)
    
    # 记录每个单词当前已经使用到的位置索引
    current_pos = {word: 0 for word in pos_map}
    # 跟踪当前已匹配到的ordered_list中的最大索引
    current_max_idx = -1
    
    result = []
    for word in unordered_list:
        # 获取当前单词在ordered_list中可用的下一个位置
        available_pos = pos_map[word][current_pos[word]]
        
        if available_pos > current_max_idx:
            # 符合排序规则，添加原单词并更新进度
            result.append(word)
            current_max_idx = available_pos
            current_pos[word] += 1
        else:
            # 违反排序规则，添加带标记的单词
            result.append(f"{marker}{word}")
    
    return result

# 示例调用
ordered_list  = ['a', 'aba', 'abaá', 'ababillarse', 'ababol', 'abacá', 'abacal', 'abacalero', 'abacería', 'abacero', 'abacial', 'ábaco', 'abacora', 'abacorar', 'abad', 'abad', 'abada', 'abadejo', 'abadengo', 'abadernar', 'abadesa', 'abadí', 'abadía', 'abadía', 'abadiado', 'abadiato', 'abajadero', 'abajamiento', 'ábax', 'aceite', 'aceite', 'ancianos', 'ár', 'arquitrabe', 'arquitrabe']

unordered_list = ['a', 'ancianos', 'aba', 'abaá', 'ababillarse', 'ababol', 'ár', 'abacá', 'abacal', 'abacalero', 'abacería', 'aceite', 'abacero', 'abacial', 'abadía', 'ábaco', 'ábax', 'arquitrabe', 'abacora', 'abacorar', 'abad', 'abad', 'abada', 'abadejo', 'abadengo', 'abadernar', 'abadesa', 'abadí', 'abadía', 'abadiado', 'abadiato', 'abajadero', 'abajamiento', 'aceite', 'arquitrabe']

result_list = get_correct_order_with_marker(ordered_list, unordered_list)
print(result_list)

输出结果与期望完全一致：

['a', '$ancianos', 'aba', 'abaá', 'ababillarse', 'ababol', '$ár', 'abacá', 'abacal', 'abacalero', 'abacería', '$aceite', 'abacero', 'abacial', '$abadía', 'ábaco', '$ábax', '$arquitrabe', 'abacora', 'abacorar', 'abad', 'abad', 'abada', 'abadejo', 'abadengo', 'abadernar', 'abadesa', 'abadí', 'abadía', 'abadiado', 'abadiato', 'abajadero', 'abajamiento', 'aceite', 'arquitrabe']

代码说明 #

1. pos_map：存储每个单词在ordered_list中的所有出现位置，解决重复元素的位置跟踪问题
2. current_pos：记录每个单词已使用的位置索引，确保重复元素按顺序匹配
3. current_max_idx：跟踪当前已匹配到的ordered_list最大索引，确保后续元素必须在该索引之后才符合规则
4. 遍历过程中，通过对比当前元素的可用位置与current_max_idx，判断是否需要标记

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