求将含插入/删除/移动的集合操作序列转换为diff的算法

算法实现思路 #

核心是跟踪每个元素的位置全生命周期变化，再从最终状态反推最简diff，具体分三步：

1. 维护元素位置映射

需要两个核心数据结构：

• element_pos：字典，记录每个元素（原始元素/插入的新元素）的当前位置
• pos_elements：列表，按当前位置存储元素ID，方便快速查找位置对应的元素
• 额外维护inserted_elements（记录插入的新元素）和orig_deleted（记录被删除的原始元素）

对每个操作的处理逻辑：

• 插入I(pos)：生成新元素ID，插入到pos_elements的对应位置，更新该位置之后所有元素的位置映射，同时记录新元素到inserted_elements
• 删除D(pos)：从pos_elements中移除对应位置的元素，如果是原始元素则加入orig_deleted，如果是插入元素则从inserted_elements移除，然后更新后续元素的位置映射
• 移动M(from,to)：把pos_elements中from位置的元素移到to位置，更新该元素的位置映射，同时调整路径上元素的位置（比如to < from时，to到from-1的元素位置+1；反之则from+1到to的元素位置-1）

2. 生成最简Diff

从最终的元素状态反推：

• 插入操作：收集所有未被删除的插入元素，按最终位置排序，生成I(pos)
• 删除操作：收集所有被删除的原始元素，按原始位置排序，生成D(orig_pos)
• 移动操作：收集所有未被删除且最终位置≠原始位置的原始元素，生成M(orig_pos, final_pos)（插入元素的移动直接等价于插入到最终位置，无需单独记录）

3. 冗余操作化简

自动消除以下冗余：

• 插入后立刻删除的元素：直接移除这两个操作
• 多次移动同一元素：只保留最终位置的移动（或转换成插入/删除，视情况）
• 连续插入/删除的位置调整：自动转换成最终等价的位置

伪代码示例 #

def simplify_operations(operations, original_elements):
    # 初始化数据结构
    element_pos = {elem: idx for idx, elem in enumerate(original_elements)}
    pos_elements = original_elements.copy()
    inserted = set()
    orig_deleted = set()
    new_id_counter = 0

    for op in operations:
        if op.startswith("I"):
            # 解析插入位置
            pos = int(op.strip("I()"))
            new_id = f"new_{new_id_counter}"
            new_id_counter += 1
            # 执行插入
            pos_elements.insert(pos, new_id)
            inserted.add(new_id)
            # 更新后续元素位置
            for idx in range(pos + 1, len(pos_elements)):
                elem = pos_elements[idx]
                element_pos[elem] = idx
            element_pos[new_id] = pos

        elif op.startswith("D"):
            pos = int(op.strip("D()"))
            elem_to_delete = pos_elements.pop(pos)
            # 更新删除记录
            if elem_to_delete in element_pos:
                del element_pos[elem_to_delete]
            if elem_to_delete in original_elements:
                orig_deleted.add(elem_to_delete)
            elif elem_to_delete in inserted:
                inserted.remove(elem_to_delete)
            # 更新后续元素位置
            for idx in range(pos, len(pos_elements)):
                elem = pos_elements[idx]
                element_pos[elem] = idx

        elif op.startswith("M"):
            from_pos, to_pos = map(int, op.strip("M()").split(","))
            elem_to_move = pos_elements.pop(from_pos)
            pos_elements.insert(to_pos, elem_to_move)
            # 更新移动元素的位置
            element_pos[elem_to_move] = to_pos
            # 调整中间元素的位置
            if to_pos < from_pos:
                # to_pos 到 from_pos-1 的元素位置+1
                for idx in range(to_pos, from_pos):
                    elem = pos_elements[idx]
                    element_pos[elem] = idx
            else:
                # from_pos 到 to_pos-1 的元素位置-1
                for idx in range(from_pos, to_pos):
                    elem = pos_elements[idx]
                    element_pos[elem] = idx

    # 生成最终diff
    diff = []
    # 处理插入：按位置排序
    sorted_inserts = sorted([(element_pos[elem], elem) for elem in inserted], key=lambda x: x[0])
    for pos, _ in sorted_inserts:
        diff.append(f"I({pos})")
    # 处理删除：按原始位置排序
    sorted_deletes = sorted([(original_elements.index(elem), elem) for elem in orig_deleted], key=lambda x: x[0])
    for orig_pos, _ in sorted_deletes:
        diff.append(f"D({orig_pos})")
    # 处理移动：原始元素位置变化且未被删除
    sorted_moves = []
    for orig_pos, elem in enumerate(original_elements):
        if elem in element_pos and element_pos[elem] != orig_pos:
            sorted_moves.append((orig_pos, element_pos[elem]))
    for orig_pos, final_pos in sorted_moves:
        diff.append(f"M({orig_pos},{final_pos})")

    return diff

验证示例 #

用你的第一个示例测试：

operations = ["I(0)", "I(0)"]
original_elements = []  # 假设原始集合为空
print(simplify_operations(operations, original_elements))
# 输出: ['I(0)', 'I(1)']，符合预期

再测试M(1,0), D(0)：

operations = ["M(1,0)", "D(0)"]
original_elements = ["A", "B"]  # 原始集合两个元素
print(simplify_operations(operations, original_elements))
# 输出: ['D(1)']，符合预期

内容的提问来源于stack exchange，提问作者Srđan Rašić