根据 dict 的给定依赖项，按顺序迭代列表

Question

我有一个列表 lst，我想使用函数 f:

迭代转换列表中的每个元素

lst = ['a', 'b', 'c', 'd', 'e', 'f', 'g']

def f(x):
    # do something
    return x

我可以对列表迭代应用此转换：

new_lst = [f(x) for x in lst]

到目前为止一切顺利。现在我们要介绍 lst 中处理元素的顺序。 dict ensure_transformed 描述了在处理给定元素之前需要转换的元素列表：

ensure_transformed = {'a' : ['b', 'e'],
                      'b' : ['e', 'f'],
                      'c' : ['a', 'd'],
                      'd' : [],
                      'e' : [],
                      'f' : []
                      }

解释是——变换前a，变换b和e，变换前b，变换e和f等等。

('d' : []的意思是在[=24=之前不需要处理任何元素。g在ensure_transformed中不存在意味着g不应该'不变形。)

如何使用函数 f 转换 lst，同时确保从 ensure_transformed 开始排序？

table 上的选项：

使用递归遍历列表，同时跟踪已经转换的元素。这种方法管理起来很麻烦。
使用字典重新排序列表，然后遍历列表。我还没有尝试过这种方法，但它看起来很有希望。

我对其他方法持开放态度。

Answer 1

ensure_transformed字典描述了一个有向图，其中{'a': ['b', 'e']}表示有一条边b → a和一条边e → a。

假设图没有环，你的任务相当于对它应用topological sorting，你可以找到各种算法。

Answer 2

正如@CristianCiupitu 在评论中提到的，现在使用 graphlib 模块可以很容易地使用 Python 3.9 来做到这一点：

import graphlib
lst = ['a', 'b', 'c', 'd', 'e', 'f', 'g']

def f(x): return x.upper() #for example

ensure_transformed = {'a' : ['b', 'e'],
                      'b' : ['e', 'f'],
                      'c' : ['a', 'd'],
                      'd' : [],
                      'e' : [],
                      'f' : []
                      }

ts = graphlib.TopologicalSorter(ensure_transformed)

processed = [f(x) for x in ts.static_order()]
print(processed)
#prints ['E', 'F', 'D', 'B', 'A', 'C']

根据 dict 的给定依赖项，按顺序迭代列表

Iterate over list with sequence according to given dependencies from dict

python

iteration

graph-theory

sequence