时间戳

首页 > 解决方案 > 如何获得在python中复制文件的正确顺序？

python - 如何获得在python中复制文件的正确顺序？

问题描述

我正在使用python复制一些文件。但我无法获得正确的复印顺序。

假设我有一堂课：

class Info:
    def __init__(self, source: str, destination: str):
        self.source = source
        self.destination = destination

我有一个清单Info。

复制顺序的规则是：

如果 A.destination 包含 B.source，则将 B 放在 A 后面。

例如这里我们有三个Info

 Id        source         destination
Info1      Root/A    ->    Root/B/A
Info2      Root/B    ->    Root/D/B
Info3      Root/C    ->    Root/A/C

Info1.destination 包含 Info2.source，所以把 Info2 放在 Info1 后面，

Info3.destination 包含 Info1.source，所以将 Info1 放在 Info3 后面。

最后的顺序是[Info3, Info1, Info2]

我认为最大的困难是有些Info无法比较。

有没有一些有效的算法来实现这一点？谢谢！

标签： pythonalgorithmsortingtree

解决方案

你可以这样做，我在这里topological sort找到一个版本：

from collections import deque
from collections import defaultdict

GRAY, BLACK = 0, 1

def topological(graph):
    order, enter, state = deque(), set(graph), {}

    def dfs(node):
        state[node] = GRAY
        for k in graph.get(node, ()):
            sk = state.get(k, None)
            if sk == GRAY: raise ValueError("cycle")
            if sk == BLACK: continue
            enter.discard(k)
            dfs(k)
        order.appendleft(node)
        state[node] = BLACK

    while enter: dfs(enter.pop())
    return order

测试代码：

graph = defaultdict(list)
graph['A'].append('B')
graph['B'].append('D')
graph['C'].append('A')

src_info = {'A': 'Info1', 'B': 'Info2', 'C': 'Info3'}
res = [src_info[c] for c in topological(graph) if c in src_info]

print(res)

输出：

['Info3', 'Info1', 'Info2']

推荐阅读