2 
INPUT:-
mainlist:[12345,23456,09768]

Need to construct the following dependency graph

12345 has 01242(internal dep),34567(externaldep)
01242 has  23456(internaldep),56789,32345(externaldep)
34567  has 11111(internal dep),no external dependencies
23456 has 33456(internaldep),no external dependencies
56789 no dependencies
32345 no dependencies
11111 no dependencies
33456 no dependencies
09768 has 12222(internal dep),34333(External dep)
12222 no dependencies
34333 no dependencies 

OUTPUT:-

[12345,01242,34567,23456,56789,32345,11111,33456,09768,12222,34333]

我有一些数据库对象，它们像上面的依赖项一样相互完全链接......我想做的是编写一个算法来检索该信息并将所有这些表示为一个图形。现在我正在编写一个伪代码，然后我应该能够编写 python 实现这似乎是一个递归算法，这就是我卡住的地方！

对于主列表中的每个项目，我试图递归地找出内部依赖和外部依赖，直到没有依赖并创建一个包含所有更改的列表。

build_dep_list=[]
local_list=[]
for each item in mainlist:
         local_list.append(item)
    build_dep_list.append(item)
    for  each localitem in local_list:
        head = localitem
        internal_dep_list =getinternaldep(change)
        external_dep_list= getexternaldep(change)
        append.internal_dep_list.local_list
        append.external_dep_list.local_list
        append.internal_dep_list.build_dep_list
        append.external_dep_list.build_dep_list
        delete(head).local_list

def getinternaldep:
    //code1

def getexternaldep:
    //code2
4

1 回答 1

1

一个可能的递归解决方案。

这是作为列表存储在字典中的模拟依赖数据。根据从数据库返回给您的数据格式，修改标记的行，以便将返回的数据转换为列表。

mainlist = ['12345', '23456' , '09768']

internal_dep = {
    '12345': ['01242'],
    '01242': ['23456'],
    '34567': ['11111'],
    '23456': ['33456'],
    '56789': [],
    '32345': [],
    '11111': [],
    '33456': [],
    '09768': ['12222'],
    '12222': [], 
    '34333': [],
    }

external_dep = {
    '12345': ['34567'],
    '01242': ['56789', '32345'],
    '34567': [],
    '23456': [],
    '56789': [],
    '32345': [],
    '11111': [],
    '33456': [],
    '09768': ['34333'],
    '12222': [],
    '34333': []
    }

递归函数分别获取内部和外部依赖数据

def getinternaldep(item):
    local_list = []
    temp_list = []
    # Change this line depending on data format
    temp_list.extend(internal_dep[item])
    local_list.extend(temp_list)
    for new_item in temp_list:
        internal_dep_list = getinternaldep(new_item)
        local_list.extend(internal_dep_list)
    return local_list

def getexternaldep(item):
    local_list = []
    temp_list = []
    # Change this line depending on data format
    temp_list.extend(external_dep[item])
    local_list.extend(temp_list)
    for new_item in temp_list:
        external_dep_list = getexternaldep(new_item)
        local_list.extend(external_dep_list)
    return local_list

调用递归函数的主函数

build_dep_list = []
for item in mainlist:
    build_dep_list.append(item)
    internal_dep_list = getinternaldep(item)
    external_dep_list = getexternaldep(item)
    build_dep_list.extend(internal_dep_list)
    build_dep_list.extend(external_dep_list)
print build_dep_list

和输出

['12345', '01242', '23456', '33456', '34567', '23456', '33456', '09768', '12222', '34333']

顺序是 mainlist item -> int dep -> ext dep -> next mainlist item -> int dep -> ext dep 依此类推。

编辑：

这是一个带有一个递归函数的稍微干净的解决方案。

def _getdep(item):
    local_list, temp_list = [], []
    temp_list.extend(internal_dep[item])
    temp_list.extend(external_dep[item])
    local_list.extend(temp_list)
    for new_item in temp_list:
        local_list.extend(_getdep(new_item))
    return local_list

build_dep_list = []
for item in mainlist:
    build_dep_list.append(item)
    build_dep_list.extend(_getdep(item))

print build_dep_list

['12345', '01242', '34567', '23456', '56789', '32345', '33456', '11111', '23456', '33456', '09768', '12222', '34333']

输出仍然不是您想要的。您可以通过一些数据结构工作来调整它。

于 2013-04-26T10:18:48.570 回答