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']

順序は、メインリスト項目 -> int dep -> ext dep -> 次のメインリスト項目 -> int dep -> ext dep などです。

編集：

これは、1 つの再帰関数を使用した、ややクリーンなソリューションです。

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 に答える