这是建立在上一个问题的基础上的解决一个简单的有依赖关系的打包组合 https://stackoverflow.com/questions/49948256/solve-a-simple-packing-combination-with-dependencies，尽管无需查看该问题即可理解这一问题。
这个问题询问计算部分有序集的线性扩展数量的最快方法。
在给定对象的任意顺序的情况下，这种部分排序的列表可以可视化为打包配置的可行性。问题相当于，如果块一旦放置就无法移动，那么为实现所示的包装配置而交给您的所有块的可能顺序是什么？
在这个例子中，需要放置所有块ABCDEFG，A、B、C、D的依赖关系：set{}，E：set{A，B}，F：set{B，C} G：set{C， D}。
通过检查7个块的所有排列并统计满足依赖关系的数量，可以获得完成偏序集的所有可能性。上一篇文章中的 גלעד ברקן 提供了一种更快的替代方案，他使用了一种图形结构，如果在已经探索的节点中不满足依赖关系，该结构会终止对分支的进一步搜索。
nodes = {
'A': {
'neighbours': ['B','C','D','E','F','G'], 'dependency': set()},
'B': {
'neighbours': ['A','C','D','E','F','G'], 'dependency': set()},
'C': {
'neighbours': ['A','B','D','E','F','G'], 'dependency': set()},
'D': {
'neighbours': ['A','B','C','E','F','G'], 'dependency': set()},
'E': {
'neighbours': ['C','D','F','G'], 'dependency': set(['A','B'])},
'F': {
'neighbours': ['A','D','E','G'], 'dependency': set(['B','C'])},
'G': {
'neighbours': ['A','D','E','G'], 'dependency': set(['C','D'])},
}
def f(key, visited):
if len(visited) + 1 == len(nodes):
return 1
if nodes[key]['dependency'] and not nodes[key]['dependency'].issubset(visited):
return 0
result = 0
for neighbour in nodes[key]['neighbours']:
if neighbour not in visited:
_visited = visited.copy()
_visited.add(key)
result += f(neighbour, _visited)
return result
print 2 * f('A', set()) + 2 * f('B', set()) # exploiting symmetry
我的问题是，是否有办法在不失通用性的情况下进一步优化 גלעד ברקן 的算法？如果依赖项很少并且列表可以进一步分解为独立的子列表，我可能可以使其更快，但对于这个特定的示例来说情况并非如此。
