基于文件版本关联的工单交付顺序排序算法实现（基础Python）

核心思路 #

你的问题本质是依赖排序问题：同一文件的工单存在先后依赖（先签出的必须先交付，后签出的需等待前者释放文件），这完全符合拓扑排序的应用场景。我们可以用Kahn拓扑排序算法，仅用基础Python的字典、列表等结构实现，高效支持大数据集。

步骤详解 #

1. 数据预处理：按文件分组并排序 #

首先需要将工单按文件路径分组，同一文件下的工单按签出先后顺序排序（先签出的在前，即需要先交付）。假设你能获取每个工单在对应文件中的签出顺序（或通过工单ID提取版本顺序），处理逻辑如下：

from collections import defaultdict

# 示例原始数据：(工单ID, 文件路径, 签出顺序)，签出顺序1为最早
sample_data = [
    ("t_256", "path/to/file/B", 1),
    ("t_43", "path/to/file/B", 2),
    ("t_21", "path/to/file/D", 1),
    ("t_50", "path/to/file/D", 2),
    ("t_40", "path/to/file/D", 3),
    ("t_30", "path/to/file/C", 1),
    ("t_20", "path/to/file/C", 2),
]

# 按文件路径分组
file_tickets = defaultdict(list)
for ticket, path, order in sample_data:
    file_tickets[path].append((order, ticket))

# 每个文件内按签出顺序排序，得到交付先后序列
for path in file_tickets:
    file_tickets[path].sort()
    file_tickets[path] = [ticket for _, ticket in file_tickets[path]]

处理后file_tickets会得到每个文件对应的工单交付顺序，比如path/to/file/B对应['t_256', 't_43']。

2. 构建依赖图与入度字典 #

基于分组后的工单序列，构建两个核心数据结构：

• 邻接表：记录每个工单完成后可交付的后续工单（即依赖当前工单的工单）
• 入度字典：记录每个工单需要等待多少个前置工单完成

adjacency = defaultdict(list)
in_degree = {}

# 初始化所有工单的入度为0
all_tickets = set()
for path in file_tickets:
    for ticket in file_tickets[path]:
        all_tickets.add(ticket)
        in_degree[ticket] = 0

# 遍历每个文件的工单序列，添加依赖关系
for path in file_tickets:
    tickets = file_tickets[path]
    for i in range(len(tickets) - 1):
        prev_ticket = tickets[i]
        curr_ticket = tickets[i+1]
        adjacency[prev_ticket].append(curr_ticket)
        in_degree[curr_ticket] += 1

比如对于path/to/file/D的序列['t_21', 't_50', 't_40']，会建立t_21 → t_50、t_50 → t_40的依赖，t_50的入度为1，t_40的入度为1。

3. 执行Kahn拓扑排序 #

通过队列处理入度为0的工单（无前置依赖，可立即交付），逐步推导所有工单的交付顺序：

from collections import deque

# 初始化队列，加入所有无前置依赖的工单
queue = deque()
for ticket in in_degree:
    if in_degree[ticket] == 0:
        queue.append(ticket)

delivery_order = []

while queue:
    current_ticket = queue.popleft()
    delivery_order.append(current_ticket)
    # 更新后续工单的入度
    for neighbor in adjacency.get(current_ticket, []):
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)

# 检查是否存在循环依赖（工单场景一般不会出现）
if len(delivery_order) != len(all_tickets):
    print("检测到循环依赖，无法确定交付顺序")
else:
    print("工单交付顺序（从早到晚）：")
    for ticket in delivery_order:
        print(ticket)

结果说明 #

运行上述代码后，会输出符合要求的交付顺序：

• 独立的工单组（如t_256/t_43、t_30/t_20、t_21/t_50/t_40）之间顺序可任意（因为无共享文件，可并行交付）
• 同一文件内的工单严格按签出顺序排列（如t_21必须在t_50前交付）

适配大数据集的优势 #

• 时间复杂度为O(V + E)（V为工单数，E为依赖关系数），线性复杂度适合大规模数据
• 仅使用Python标准库的基础结构，无需额外依赖
• 逻辑模块化，可轻松调整排序规则（比如根据工单ID提取版本号排序）

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