建立名單出來字典

的我有一本字典，對於每個關鍵列出其依賴關係：建立名單出來字典

parent[2] = 1 (2 depends on 1) 
parent[3] = 1 (3 depends on 1) 
parent[4] = {2,3} (4 depends on 2, or 4 depends on 3)

我想建立羅列出這本字典：

[4,2,1] 
[4,3,1]

我我懷疑我應該使用遞歸算法。任何提示？

編輯：這是我到目前爲止有：

如何調用遞歸函數：

var result = new List<List<Node<TData, TId>>>(); 
GetResult(parent, target, result); 
return result;

和遞歸函數本身：

private static List<Node<TData, TId>> GetResult<TData, TId>(Dictionary<Node<TData, TId>, List<Node<TData, TId>>> parent, Node<TData, TId> index, 
    List<List<Node<TData, TId>>> finalList) 
    where TData : IIdentifiable<TId> 
    where TId : IComparable 
{ 
    var newResult = new List<Node<TData, TId>> { index }; 

    if (parent.ContainsKey(index)) 
    { 
     if (parent[index].Count == 1) 
     { 
      return new List<Node<TData, TId>> { index, parent[index].First()}; 
     } 

     foreach (var child in parent[index]) 
     { 
      var temp = newResult.Union(GetResult(parent, child, finalList)).ToList(); 
      finalList.Add(temp); 
     } 
    } 

    return newResult; 
}

來源

2014-10-04 Maria Ines Parnisari

是的，它應該是遞歸。你面臨的問題是什麼？ – Dmitry 2014-10-04 23:36:08

你*幾乎*尋找*拓撲排序*算法。 *幾乎*因爲您的列表意味着*或*而不是*和*。有* A的可能性取決於B和C *嗎？ – 2014-10-04 23:38:43

@Dmitry，我已編輯帖子以包含我的代碼。它不適用於'dict [4] = 1'的情況，它應該只返回一個包含'[4,1]'的列表，但事實並非如此。 – 2014-10-05 03:48:37

你可以嘗試爲您的需要進行修改下面的代碼：

public static List<List<int>> FindParents(Dictionary<int, List<int>> parents, int index) 
{ 
    List<int> prefix = new List<int>(); 
    List<List<int>> results = new List<List<int>>(); 
    FindParentsInternal(parents, index, prefix, results); 
    return results; 
} 

private static void FindParentsInternal(Dictionary<int, List<int>> parents, int index, 
    List<int> prefix, List<List<int>> results) 
{ 
    var newPrefix = new List<int>(prefix) { index }; 
    if (!parents.ContainsKey(index)) 
    { 
     results.Add(newPrefix); 
     return; 
    } 
    parents[index].ForEach(i => FindParentsInternal(parents, i, newPrefix, results)); 
}

用法：

Dictionary<int, List<int>> parents = new Dictionary<int, List<int>> 
    { 
     { 2, new List<int> { 1 } }, 
     { 3, new List<int> { 1 } }, 
     { 4, new List<int> { 2, 3 } } 
    }; 

var t = FindParents(parents, 4);

來源

2014-10-05 08:25:42 Dmitry

我會試試這個，謝謝！ – 2014-10-05 16:23:37

你的嘗試結果是什麼？我很好奇。 – Dmitry 2014-10-05 20:32:59

是的，它工作:)謝謝！ – 2014-10-05 20:33:43

您可以受益通過保存結果字典 - 這樣你就不需要重新計算它們。

Dictionary<Int, Set<Int>> results; 

Set<Int> getResult(int index) { 
    Set<Int> dictResult = results.get(index); 
    if(dictResult != null) { 
    // result has already been computed 
    return dictResult; 
    } else { 
    // compute result, store in dictResult 
    Set<Int> newResult = // compute dependency set 
    dictResult.put(index, newResult); 
    return newResult; 
    } 
}

至於// compute dependency list一部分，你可以這樣做以下：

Set<Int> newResult = new Set(index); 
if(dict.containsKey(index)) { 
    List<Int> dependencies = dict.get(index); 
    foreach(int subIndex in dependencies) { 
    newResult = newResult.union(getResult(subIndex)); 
    } 
}

您的基本情況是，當指數不dict（即dict.containsKey返回false），例如1爲您提供的數據。

來源

2014-10-05 00:08:29

建立名單出來字典

回答

相關問題