时间戳

首页 > 解决方案 > 基于 Id 和 Dependency 对工单进行排序的算法

python - 基于 Id 和 Dependency 对工单进行排序的算法

问题描述

我有一个订单清单：

id, dependency_id
1,  2
1,  3
3,  4
5,  2
3,  6

我必须输出这样的东西：

Id: 1, Name: Order 1
Dependencies
   Id: 2, Name: Order 2
   Id: 3, Name: Order 3
   Dependencies
      Id: 4, Name: Order 4
      Id: 6, Name: Order 6
Id: 5, Name: Order 5
Dependencies
   Id: 2, Name: Order 2

我应该使用哪种递归算法？我被困住了

这是我到目前为止所拥有的：

dependencies = {}
def read():
  f = open("dependencies.txt", "r")
  # contents = f.read() #reads the whole file
  #print(contents) #prints everything
  #print(contents[0]) #prints first letter
  lines = f.readlines()
  for i in range(1, len(lines)):
    dep = lines[i].split(",")
    dep[1] = dep[1].rstrip()
    try:
      depList = dependencies.get(dep[0], [])
      depList.append(dep[1])
      dependencies[dep[0]] = depList
    except:
      dependencies[dep[0]] = [dep[1]]
if __name__ == "__main__":
  read()

这将返回：{'1': ['2', '3'], '3': ['4', '6'], '5': ['2']}

标签： pythonalgorithm

解决方案

你可以做这样的事情；

#-*- coding:utf-8 -*-

table = [(1, 2), (1, 3), (3, 4), (5, 2), (3, 6)]

deps = {}
for k, d in table:
    if k not in deps:
        deps[k] = {}
    if d not in deps:
        deps[d] = {}

    deps[k][d] = True
    deps[d][k] = True

def p(a, d, stack):
    print "%sId: %d, Name: Order %d" % (d * "  ", a, a)
    stack.append(a)
    for b, v in deps[a].iteritems():
        if not b in stack:
            print (d*"  ") + " Dependencies"
            p(b, d+1, stack)

for k, d in table:
    p(k, 0, [])

推荐阅读