如何根据列表项的依赖关系重新排序列表？

问题描述 #

现有示例列表：

list = ["Create Apple Pie from apples, pie crust etc", "Create pie crust from eggs, flour etc", "Create x from y", "create y from z"]

需求是将所有独立项排在其依赖项之前，排序后目标列表如下：

list = ["Create y from z", "create x from y", "Create pie crust from eggs...", "Create apple pie from pie crust"]

列表项遵循通用格式：Create abc from xyz。我已尝试用正则表达式提取项目名称，但不清楚如何遍历并完成重排，恳请技术解答。

解决步骤 #

1. 提取任务与依赖关系 #

首先用正则表达式精准提取每个任务的名称和它依赖的所有项，不区分大小写：

import re
from collections import defaultdict

tasks = ["Create Apple Pie from apples, pie crust etc", "Create pie crust from eggs, flour etc", "Create x from y", "create y from z"]

# 正则匹配：提取任务名和依赖项
pattern = re.compile(r'create\s+(.*?)\s+from\s+(.*?)(?:\s+etc)?$', re.IGNORECASE)
task_deps = {}
all_tasks = set()
all_deps = set()

for task_str in tasks:
    match = pattern.match(task_str.strip())
    if match:
        task_name = match.group(1).strip()
        deps_str = match.group(2).strip()
        # 拆分依赖项（按逗号分隔）
        dependencies = [dep.strip() for dep in deps_str.split(',')]
        task_deps[task_name] = {dep for dep in dependencies if dep}
        all_tasks.add(task_name)
        all_deps.update(dependencies)

2. 拓扑排序实现依赖重排 #

核心是用拓扑排序确保依赖项优先，步骤如下：

• 找出无依赖的初始任务
• 依次移除这些任务，更新剩余任务的依赖计数
• 重复直到所有任务处理完成

# 计算每个任务的入度（依赖的数量）
in_degree = defaultdict(int)
for task in all_tasks:
    in_degree[task] = len(task_deps.get(task, set()))

# 初始化队列：没有依赖的任务
queue = [task for task in all_tasks if in_degree[task] == 0]
sorted_task_names = []

while queue:
    current = queue.pop(0)
    sorted_task_names.append(current)
    # 更新依赖当前任务的其他任务的入度
    for task, deps in task_deps.items():
        if current in deps:
            in_degree[task] -= 1
            if in_degree[task] == 0:
                queue.append(task)

# 映射回原字符串（处理大小写差异）
task_to_str = {}
for task_str in tasks:
    match = pattern.match(task_str.strip())
    if match:
        task_name = match.group(1).strip()
        task_to_str[task_name.lower()] = task_str

sorted_list = [task_to_str[name.lower()] for name in sorted_task_names]
print(sorted_list)

3. 输出结果 #

运行代码后将得到符合需求的排序结果：

["create y from z", "Create x from y", "Create pie crust from eggs, flour etc", "Create Apple Pie from apples, pie crust etc"]

注意事项 #

• 如果存在循环依赖（如A依赖B、B依赖A），拓扑排序会失效，需提前检测并处理
• 正则表达式可根据实际格式调整，比如依赖项含特殊字符时优化匹配规则

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